Một hôm, Chưng mang tặng bạn một hộp bánh su kem rất ngon. Tuy nhiên, ăn từng chiếc một thì thật là nhàm chán, nên bạn nảy ra một ý tưởng thú vị: ghép nhiều chiếc bánh lại rồi ăn một lần để tăng độ ngon.

Tuy nhiên, vì là người làm ra bánh, Chưng biết rằng có những cặp bánh nếu ăn cùng nhau sẽ gây ngộ độc. Dù Chưng đã cố gắng cảnh báo, bạn vẫn bất chấp, quyết tâm thử cho bằng được. Bạn được cho hai danh sách thông tin:

• Danh sách thứ nhất: độ ngon của từng chiếc bánh su kem, được đánh số từ ~1~ đến ~N~.
• Danh sách thứ hai: các cặp bánh không thể ăn cùng nhau, vì nếu ghép chung sẽ bị tạch.

Giờ đây, bạn muốn chọn ra một nhóm bánh để ăn cùng lúc sao cho:

Tổng độ ngon là lớn nhất. và không có hai bánh nào trong nhóm gây ngộ độc khi ăn cùng.

Bạn hãy tìm ra tổng độ ngon lớn nhất mà bạn có thể đạt được!

Input

• Dòng đầu tiên gồm hai số nguyên ~N, M~ với ~1 \le N \le 40~ và ~1 \le M \le 10^3~.

• Dòng tiếp theo gồm ~N~ số ~a_i~ đại diện cho độ ngon của từng chiếc bánh ~1 \le a_i \le 10^9~ .

• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u, v~ với ~1 \le u, v \le N~ và ~u \neq v~, mô tả nếu ăn su kem chỉ số ~u, v~ cùng lúc sẽ bị ngộ độc

Output

Độ ngon lớn nhất của chiếc bánh được tạo nên bằng cách ghép nhiều chiếc su kem khác lại với nhau và đảm bảo rằng khi ăn chiếc bánh đó sẽ không bị ngộ độc.

Sample Input 1

4 3
1 2 1 3
1 2
2 3
2 4

Sample Output 1

5

Giải thích:

Ta sẽ ghép các chiếc bánh vị trí 1, 3, 4 để đạt được độ ngon lớn nhất.