스터디 두 팀

문제

알고리즘 스터디원 N명(N 은 짝수)을 인원이 같은 두 팀으로 나누려 한다. i번째 사람의 실력 점수는 a_i 다. 두 팀의 실력 합 차이가 가능한 한 작아야 한다. 그런데 '이 둘은 같은 팀이어야 한다' 는 요청이 M개 들어왔다. 요청은 이어진다. 1과 2가 같은 팀, 2와 3이 같은 팀이면 1과 3도 같은 팀이다. 요청을 모두 지키면서 두 팀의 실력 합 차이의 최솟값을 구하라. 요청을 모두 지키며 인원을 똑같이 나눌 수 없으면 -1 을 출력한다.

입력

첫째 줄에 N 과 M 이 주어진다. (2 ≤ N ≤ 16, N 은 짝수, 0 ≤ M ≤ 20)

둘째 줄에 a_1 … a_N 이 주어진다. (1 ≤ a_i ≤ 100)

다음 M개 줄에 같은 팀이어야 하는 두 사람의 번호 u, v 가 주어진다. (1 ≤ u, v ≤ N) u 와 v 가 같을 수도 있고, 같은 요청이 여러 번 나올 수도 있다.

출력

실력 합 차이의 최솟값을 출력한다. 불가능하면 -1 을 출력한다.

4 1
1 2 3 4
1 4

0

4 2
5 5 5 5
1 2
2 3

-1

출처: Devin.KR 자체 제작