Nicole

Nicole은 물리학과 천문학 책을 즐겨 읽어서 타원형 속삭임의 방을 잘 안다. 커다란 타원형 방에서는 한쪽 초점에 선 사람이 다른 초점에 선 사람의 말을 아주 또렷하게 듣는다. 천장이 긴 회전 타원체의 일부처럼 생겼으면 이 효과가 더 강해진다. 미국 국회의사당의 국립 조각상 전당과 솔트레이크시티 템플 스퀘어의 태버내클이 이런 방이다.

어느 전국 대회장은 모양이 불규칙했는데, 일부 자리 쌍 사이에 똑같은 성질이 나타났다. 그런 쌍을 이루는 두 자리는 서로 초점 반사 관계라서, 한쪽에 앉은 사람이 다른 쪽에 앉은 사람의 말을 또렷하게 듣는다. 대회 중에 이런 일이 일어나면 안 되므로, 서로 말이 들리는 두 자리에 두 팀이 함께 앉을 수 없다. 자리마다 만족도도 정해져 있다. 만족도는 에어컨, 조명, 음식과 얼마나 가까운지에 따라 달라진다.

자리의 개수, 각 자리의 만족도, 서로 말이 또렷하게 들리는 자리 쌍이 모두 주어진다. 일부 자리를 사용 금지로 표시해서 남는 자리가 두 개 이상이고, 남는 자리끼리는 서로 말이 또렷하게 들리지 않게 만들어라. 이때 남는 자리의 만족도 합이 가장 큰 값을 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 100$).

각 테스트 케이스의 첫째 줄에는 자리의 개수 $N$과 서로 말이 또렷하게 들리는 자리 쌍의 개수 $M$이 공백으로 구분되어 주어진다 ($2 \le N \le 20$, $0 \le M \le N(N-1)/2$). 자리에는 $1$번부터 $N$번까지 번호가 붙어 있다.

다음 줄에는 $N$개의 양의 정수가 공백으로 구분되어 주어진다. 순서대로 1번 자리, 2번 자리, ..., $N$번 자리의 만족도이고, 각 값은 1000 이하이다.

다음 $M$개 줄에는 서로 다른 두 정수 $u$와 $v$가 공백으로 구분되어 주어진다 ($1 \le u, v \le N$). $u$번 자리에 앉은 사람과 $v$번 자리에 앉은 사람은 서로의 말을 또렷하게 듣는다. 같은 쌍이 두 번 주어지는 경우는 없다.

각 테스트 케이스마다 Case n: R 형식으로 한 줄씩 출력한다. $n$은 1부터 시작하는 테스트 케이스 번호이고, $R$은 남는 자리의 만족도 합의 최댓값이다. 조건을 만족하는 방법이 없으면 $R$은 -1이다.