The CSE Department of NIT Trichy is not particularly renowned for its eye-candy. Noticing this, Paarth decides to distribute some candies throughout the department. The department consists of n rooms. There are corridors connecting certain pairs of rooms. Being very frugal, the corridors are designed in such a way that every pair of rooms are connected by exactly one path. Now Alpa and Syed are let loose in the department and they want to collect as many candies as possible. Alpa has hired you to help him maximize the difference between the number of candies obtained by him and Syed based on the constraint that he shall never enter any room that is visited by Syed.

More formally, you are given a tree - A connected and acyclic graph with n vertices.

Each vertex in the tree has a value associated with it (the number of candies). Note that the number of candies may be negative as well (bullies waiting to snatch your candies away.)

Given a set of vertices S, value(S) = sum of values of all vertices in set S.

Your task is to select two sets of vertices A and B such that:

1. A and B are disjoint (they have no vertex in common)
2. Every vertex in A is connected to every other vertex in A through some path;
3. Every vertex in B is connected to every other vertex in B through some path;
4. A has k1 vertices; i.e. | A | = k1
B has k2 vertices; i.e. | B | = k2
5. value(A) - value(B) is maximized.

If it is not possible to select two such components, print -1.

Constraints

2 <= n <= 200

0 < k1, k2 <= n

The values of all vertices are between -10^5 and 10^5

Input

First line contains t, the number of test cases. Each test case is as follows:

First line contains three integers: n, k1 and k2.

Next line contains n integers, the values of the n vertices.

Next n - 1 lines contain 2 integers a and b, indicating that there is an edge between vertices a and b; 0 <= a < b < n

Output

For each test case, print one line containing an integer = value(A) - value(B) .

Sample

Input:
2
7 3 3
0 1 -1 2 3 -2 -3
0 1
0 2
1 3
1 4
2 5
2 6
3 2 2
1 2 3
0 1
0 2

Output:
12
-1

Explanation:

In the first case, A = {1, 3, 4} and B = {2, 5, 6}.