mmm2

It's a well-known fact that MMM, the greatest general in history, loves traveling.
This time she is setting off to Tianjin, a city famous for stuffed-bun, with her MMM Army. Tianjin is a city with N sites. And N sites are divided into several areas. Each site belongs to exactly one area. For each area, the number of sites and the number of street connected them are equal, and each pair of sites belong to the same area, there existed at least one simple path going from one site to the other. For each pair of sites belong to different area, no streets will connect them. The deliciousness of buns in the bakehouse on the i-th site is evaluated as an integer Wi. As MMM wants to maintain Bureaucratic Government (BG for short) to her army, she would invite them to every bakehouse on their way. But there is one problem: MMM hates to visit a site twice because 2 is an ominous number to her. However, they could choose to take the subway if in need. The subway in Tianjin is well developed so they can transport from any sites to any other sites conveniently even if when they are not connected by the streets. But MMM will feel carsick if they take the subway K times or more.
Now the question is, what's the maximum total deliciousness can MMM reach without carsickness? Note that with the convenient subway the MMM Army can start and end their journey in any site.

The first line of input consist of one integer T which means T cases will follow (1≤T≤15).
Then follow T cases, each case begin with two integers N, K (1≤ N ≤ 50000, 1≤ K ≤10).
The following line contains N integer Wi, |Wi| ≤ 10^6.
Then N line follow, each line contains two integer u, v. mean there is a street between site u and site v. 1 ≤ u, v ≤ N

Just a line contains the maximum total deliciousness

1
9 3
-2 -10 3 15 11 1 10 10 -3
1 2
1 3
2 3
2 4
2 5
5 6
3 7
8 9
9 8

40

mmm's army start at city 6, and walk to city 4,the path is 6->5->2->4. total deliciousness is 1+11+(-10)+15=17.
then take subway to city 3, and then walk to city 7,the path is 3->7. total deliciousness is 3+10=13.
then take subway to city 8, and end their travel at city 8.total deliciousness is 10,
so the answer is 17+13+10=40.

2012 Asia Tianjin Regional Contest