Problem D
Paimon's Tree

Paimon has found a tree with $(n + 1)$ initially white vertices in her left pocket and decides to play with it. A tree with $(n + 1)$ nodes is an undirected connected graph with $n$ edges.

Paimon will give you an integer sequence $a_1, a_2, \cdots , a_ n$ of length $n$. We first need to select a vertex in the tree and paint it black. Then we perform the following operation $n$ times.

During the $i$-th operation, we select a white vertex $x_ i$ which is directly connected with a black vertex $y_ i$ by an edge, set the weight of that edge to $a_ i$ and also paint $x_ i$ in black. After these $n$ operations we get a tree whose edges are all weighted.

What’s the maximum length of the diameter of the weighted tree if we select the vertices optimally? The diameter of a weighted tree is the longest simple path in that tree. The length of a simple path is the sum of the weights of all edges in that path.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 5 \times 10^3$) indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 150$) indicating the length of the sequence.

The second line contains $n$ integers $a_1, a_2, \cdots , a_ n$ ($1 \le a_ i \le 10^9$) indicating the sequence.

For the following $n$ lines, the $i$-th line contains two integers $u_ i$ and $v_ i$ ($1 \le u_ i, v_ i \le n + 1$) indicating that there is an edge connecting vertex $u_ i$ and $v_ i$ in the tree.

It’s guaranteed that there are at most $10$ test cases with $n > 20$.

Output

For each test case output one line containing one integer indicating the maximum length of the diameter of the tree.

Explanation

For the first sample test case, we select the vertices in the order of $1, 3, 4, 5, 2, 6$, resulting in the weighted tree of the following image. It’s obvious that the longest simple path is of length $16$.

2
5
1 7 3 5 4
1 3
2 3
3 4
4 5
4 6
1
1000000000
1 2

16
1000000000