• Có trong tay lượng tiền bẩn khổng lồ, Pitomon nhanh chóng thâu tóm thế giới ngầm, chiêu mộ hàng ngàn đàn em và các băng đảng trên toàn vũ trụ. Tuy nhiên, quyền lực càng lớn, sự hoang tưởng càng cao. Pitomon bắt đầu ăn không ngon ngủ không yên vì sợ những kẻ dưới trướng cắn xé lẫn nhau hoặc hợp mưu lật đổ mình. Để kê cao gối ngủ, vị bạo chúa quyết định thiết lập lại trật tự: Hắn chia toàn bộ \(N\) hệ hành tinh trong đế chế thành đúng 2 Liên minh độc lập.
• Hệ hành tinh thứ \(i\) có lực lượng quân sự là \(A_i\). Điều kiện tiên quyết là những kẻ có thù hằn tuyệt đối không được xếp chung một phe. Trong quá khứ đã xảy ra các cuộc xung đột, được ghi nhận qua \(M\) cặp hành tinh có mối thù hằn với nhau. Để các phe tự kìm kẹp lẫn nhau, tổng lực lượng vũ trang của hai bên phải ngang bằng nhau nhất có thể. Nhiệm vụ của bạn là kiểm tra xem có thể phân chia các hành tinh thành 2 Liên minh thỏa mãn quy tắc thù hằn trên hay không. Nếu có, hãy tìm cách chia sao cho độ chênh lệch tổng lực lượng quân sự giữa hai Liên minh là NHỎ NHẤT. Nếu không có cách chia nào thỏa mãn, hãy báo cho Pitomon biết để hắn tìm phương án khác.

Input

• Dòng đầu tiên chứa 2 số nguyên \(N, M\) mô tả số lượng hệ hành tinh và số cặp hành tinh có mối thù hằn.
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) biểu diễn lực lượng quân sự của từng hệ hành tinh.
• \(M\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(u, v\) (\(1 \le u, v \le N, u \neq v\)) mô tả hành tinh \(u\) và hành tinh \(v\) có mối thù hằn với nhau.

Output

• Một dòng duy nhất chứa 1 số nguyên là độ chênh lệch tổng lực lượng quân sự nhỏ nhất giữa hai Liên minh.
• Nếu không thể chia thành 2 Liên minh thỏa mãn điều kiện, in ra -1.

Scoring

• Subtask 1: có 20% số điểm với \(N \le 20\)
• Subtask 2: có 30% số điểm với \(N \le 1000, M = 0\), và \(\sum_{i=1}^{N} A_i \le 50000\)
• Subtask 3: có 50% số điểm với \(N \le 2000, M \le 2000\), và \(\sum_{i=1}^{N} A_i \le 50000\)

Sample Input 1

4 2
10 20 30 40
1 2
3 4

Sample Output 1

0

Sample Input 2

3 3
10 20 30
1 2
2 3
3 1

Sample Output 2

-1

Sample Input 3

5 3
15 25 10 30 50
1 2
2 3
4 5

Sample Output 3

20

Giải thích

Ở ví dụ thứ nhất, Pitomon có thể chia thành 2 Liên minh: phe thứ nhất gồm hành tinh {1, 4} (tổng lực lượng: 10 + 40 = 50), phe thứ hai gồm hành tinh {2, 3} (tổng lực lượng: 20 + 30 = 50). Chênh lệch là 0 và không có hành tinh nào thù hằn nhau bị xếp chung.
Ở ví dụ thứ hai, ba hành tinh 1, 2, 3 đôi một thù hằn nhau. Theo luật, không thể nào xếp 3 hành tinh này vào đúng 2 Liên minh mà không có ai thù hằn nhau. Do đó kết quả là -1.