You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Em là chú cá voi chưa gặp được anh đã rơi xuống biển sâu thăm thẳm.

Anh như ngang qua, lại chẳng nghe thấy hơi thở của em.

Người ta thường gọi chú cá voi 52 Hz là chú cá voi cô đơn nhất hành tinh, bởi tiếng kêu của nó có tần số 52 Hz, cao hơn nhiều so với những chú cá voi khác, không thể giao tiếp được.

Ở thế giới nọ, nếu hai người cùng là bạn của một người khác, thì hai người đó cũng là bạn của nhau. Một nhóm bạn là một nhóm người mà mọi cặp bất kỳ trong nhóm đều là bạn của nhau. Một người cũng được coi là một nhóm bạn.

Yêu cầu

Cho $T$ test. Với mỗi test: cho $n$ số $a_1,\dots,a_n$ biểu thị “tần số” của $n$ người, và $m$ mối quan hệ bạn bè $(u,v)$.

Hãy chia toàn bộ $n$ người thành hai nhóm bạn (theo cách hiểu về nhóm bạn nêu trên) sao cho chênh lệch giữa tổng tần số của hai nhóm là nhỏ nhất có thể.

Hiển nhiên, mỗi nhóm phải có ít nhất 1 người.

Dữ liệu

Vào từ đầu vào chuẩn:

• Dòng 1: số nguyên dương $T$ ($T \le 2000$) — số test.
• Sau đó, với mỗi test:
  • Dòng đầu: số nguyên dương $n,m$.
  • Dòng tiếp: $n$ số nguyên dương $a_1,\dots,a_n$ lần lượt là tần số của người $1,\dots,n$.
  • $m$ dòng tiếp: mỗi dòng hai số $u, v$ thể hiện rằng người $u$ và người $v$ là bạn của nhau.

Kết quả

Với mỗi test, ghi ra một dòng chứa một số nguyên dương là chênh lệch tối thiểu giữa hai nhóm; trường hợp không thể chia, ghi -1.

Ví dụ

4
5 2
3 1 4 2 2
1 2
2 3
6 0
5 5 5 5 5 5
5 3
2 3 5 7 11
1 2
2 3
4 5
4 3
1 2 3 4
1 2
2 3
3 4

-1
-1
8
0

Giới hạn

Subtask 1 (50% số điểm): $n \le 1000$ cho mỗi test, $\sum n \le 10000$ trên toàn bộ input, $a_i \le 1000$, $\sum a_i \le 10000$ cho mỗi test, $\sum$ (tất cả $a_i$ trên toàn input) $\le 10000$.

Subtask 2 (50% số điểm): $n \le 10000$ cho mỗi test, $\sum n \le 100000$ trên toàn bộ input, $a_i \le 2000$, $\sum a_i \le 50000$ cho mỗi test, $\sum$ (tất cả $a_i$ trên toàn input) $\le 50000$.