Nicole

Nicole reads a lot of physics and astronomy, so she knows what an elliptical whisper chamber is. In a large elliptical room a person standing at one focus hears a person standing at the other focus remarkably well, and the effect gets stronger under a vaulted roof shaped like part of a prolate spheroid. The National Statuary Hall in the United States Capitol and the Tabernacle at Temple Square in Salt Lake City both behave this way.

At one national contest the hall had an irregular shape with the same property between some pairs of locations. The two locations of such a pair are focal reflections of each other, so a person sitting at one of them hears the person sitting at the other one clearly. That must not happen during the contest, so two teams may not sit at a pair of locations that hear each other. Every location also has a satisfaction value, which depends on how close it is to the air conditioners, the lights and the food.

You are given the number of locations, the satisfaction value of every location, and every pair of locations that hear each other clearly. Mark some locations as closed so that at least two locations stay available and no available location hears any other available location clearly. Print the largest total satisfaction value of the available locations.

The first line contains one integer $T$, the number of test cases ($1 \le T \le 100$).

Each test case starts with a line containing two integers $N$ and $M$ separated by a space. $N$ is the number of locations ($2 \le N \le 20$), numbered from $1$ to $N$, and $M$ is the number of pairs of locations that hear each other clearly ($0 \le M \le N(N-1)/2$).

The next line contains $N$ positive integers separated by spaces, the satisfaction value of location $1$, then of location $2$, and so on up to location $N$. Each of these values is at most 1000.

Each of the next $M$ lines contains two different integers $u$ and $v$ separated by a space ($1 \le u, v \le N$), meaning that a person at location $u$ and a person at location $v$ hear each other clearly. The same pair is never given twice.

For each test case print one line Case n: R, where $n$ is the number of the test case starting from 1 and $R$ is the largest total satisfaction value of the available locations. If no choice of available locations satisfies the conditions, $R$ is -1.