Problem Description
As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. But today Rikka doesn't want to do math tasks, so they begin to play some games:
Long long ago, There is a continent which has n citis and n−1 roads on it. Each city is connected to others directly or indirectly.
Now you want to build your own kingdom and make city 1 be the capital. Then you will cut off all the roads which connects a city which belong to your country and a city outside your country. Your country must satisfy the following rules:
1.City 1 must belong to your country.
2.Each pair of cities in your country can get to each other by the roads which haven't been cut off.
After cutting off the roads, actually, the continent has been cut to many unicom blocks. And then each unicom block develops into an independent state. To preserve the peace, you need to choose at most k other counties (can't be your own country) and establish diplomatic relations with them.
Each city have a prosperous value wi and the prosperous value of each country is equal to the sum of the prosperous value of the citis in it. And the stable value of your country is eaual the prosperous value of your own country plus a× the sum of the prosperous value of the countrie which have diplomatic relations with you.
Now, you need to maximal the stable value.
It is too difficult for Rikka. Can you help her?
Input
There are no more than 1000 testcases and there are no more than 3 testcase meet n,k≥100.
For each testcase, the first line contains three integers n,a,k(1≤n≤105,−103≤a≤103,0≤k≤500).
The second line contains n integers wi(−109≤wi≤109)
Then n−1 lines follow. Each line contains two numbers u,v(1≤u,v≤n) , which means there is an edge between u and v.
Output
For each testcase, print a single number -- the answer.
Sample Input
3 2 1
10 100 1000
1 2
1 3
Sample Output
2110
Hint
Your country is {1,2} and you can establish diplomatic relations with {3}. Finally the stable value is 2110.
