Open Contest 2006

During the development of delay-noise analysis theory, scientists have come upon the following problem. After they had conducted experiments they found out that some of the nodes of the circuit couldn't switch at the same time. For example, if we know that node N switches from 0 to 1, then node K can’t switch at the same moment because of logical restrictions in circuit. Each node of the circuit injects some noise into neighboring nodes while switching, and this noise can be measured. Scientists now need some fast method to calculate the maximum delay-noise that can be injected by switching aggressor-nodes.

Scientists formalize the problem in the following way. We consider a graph G = (V, E, w) consisting of vertex set V, edges se , and weight function W, such that and . For and , N(u) and N(K) denotes the set of neighboring vertices of u and K accordingly, formally defined as:

The set of vertices satisfying is called internally stable. In this problem you should find a set of internally stable vertices B such that w(B) = max{w(S)}, taken over all internally stable sets S of the given graph G.

Experiments have shown that the density of edges in considered graphs is between 20% and 90%.

Input

t – number of test cases [t <= 60]
n k – [n – number of vertices (2 <= n <= 250), k – number of edges (1 <= k <= n*(n-1)/2)]
then n integers follow (wi - weight of vertex i) [ 0 <= wi <= 2^31-1]
then k pairs of integers follow, representing the edges between vertices (si sj denotes an edge between vertices i and j) [1 <= si, sj <= n]. It is known that the total weight of all vertices in the graph doesn't exceed 10^9.

Output

For each test case output MaxWeight – the weight of a maximum internally stable set of the given graph [ 0 <= MaxWeight <= 10^9].

Example

Input :
2
5 6
10 20 30 40 50
1 2
1 5
2 3
3 4
3 5
4 5

4 4
10 4 10 14
1 2
2 3
3 4
4 1

Output :
70
20

Example illustrations: