Tại Earth-2729, có ~n~ quốc gia, quốc gia thứ ~i~ có sức mạnh quân sự ~c_i~. Hiện tại, đang có ~m~ cuộc xung đột quân sự diễn ra trên toàn cầu, cuộc xung đột thứ ~i~ giữa hai quốc gia ~u_i~ và ~v_i~.

Nhóm Azenzers muốn có những động thái để tránh tình hình chiến sự leo thang, tuy nhiên đây không phải là truyện truyện tranh Marvel, họ không hề có siêu năng lực nào cả. Vậy nên nhóm muốn thành lập một liên minh gồm một số quốc gia để hợp tác quân sự, sao cho tổng sức mạnh quân sự của các nước này là lớn nhất và không có cuộc xung đột nào đang diễn ra giữa các quốc gia được lựa chọn để hợp tác.

Hãy giúp nhóm Azenzers tìm được liên minh quân sự tốt nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~ ~(1 \le n \le 40; 0 \le m \le \frac{n \times (n-1)}{2})~.

• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~c_i~ là sức mạnh quân sự của từng quốc gia ~(1 \le c_i \le 10^9)~.

• Trong ~m~ dòng sau, mỗi dòng gồm hai số nguyên dương ~u_i, v_i~ miêu tả xung đột thứ ~i~. ~(1 \le u_i,v_i \le n; u_i \neq v_i)~

Output

• Gồm một số nguyên dương miêu tả tổng sức mạnh quân sự lớn nhất của liên minh thỏa mãn.

Scoring

• Subtask ~1~ (~20~ điểm): ~n \le 20~

• Subtask ~2~ (~30~ điểm): ~n \le 30~

• Subtask ~3~ (~50~ điểm): không có ràng buộc gì thêm.

Sample Input 1

4 2
4 9 2 1
1 4
2 4

Sample Output 1

15

Notes

Chọn quốc gia ~1~, ~2~ và ~3~.