G. Charging Power
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Being unemployed, Da7doo7 is sleeping in the middle of the day and has this dream:

Ali Zaiback is traveling between cities that form a tree structure, there are $$$n$$$ cities in total. Each city has an affection value, denoted by $$$a_i$$$. While traversing the tree, Ali can utilize his power card, which affects his power (which is initially equal to zero) by adding the affection value of the city he visits ($$$a_i$$$ can be negative, representing power drain).

Due to time constraints, Ali can visit at most $$$m$$$ different cities and use his power card no more than $$$k$$$ times. Ali cannot revisit any city, and he has the freedom to choose any city as his starting point.

You are required to determine the maximum power Ali can achieve during his journey.

Input

The first line contains a single integer $$$T$$$ $$$(1\le T\le 1000)$$$ denoting the number of test cases.

The first line of each test case contains three integers $$$n,m,k$$$ $$$(1\le k\le m\le n\le 3000)$$$ — the number of cities, the maximum number allowed for visiting different cities, and the maximum number allowed for utilizing the power card.

The second line contains an array of integers $$$a_i$$$ $$$(-10^6\le a_i\le 10^6)$$$ — the elements of the array $$$a$$$.

Each of the following $$$n-1$$$ lines of each test case contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n, u \neq v$$$) — the vertices connected by an edge. It is guaranteed that these edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^4$$$.

Output

For each test case, print the maximum power Ali can achieve in a single line.

Example
Input
2
5 3 2
3 4 7 5 2
1 2
1 3
1 4
1 5
5 3 2
3 4 7 5 2
1 2
1 3
2 4
2 5
Output
12
11