Emili has decided to buy a literal tree to put in her bedroom! She wants to decorate it with ~N~ pieces of candy, attached together with strings. Each piece of candy has a tastiness value of ~t_i~ that Emili assigns it. Some candy, such as Tootsie rolls, are so bad that they have a negative tastiness value! There are exactly ~N-1~ strings connecting the candy, and all pieces of candy are connected together by the strings. The candies are numbered from ~1~ to ~N~. Candy ~1~ is at the very top of the tree, which is known as the root of the tree.

Having all the candy sitting on the tree has made Emily hungry! She plans to choose at most ~K~ pieces of candy and eat all of the candy at and below it on the tree. In other words, she will eat all the candy in a candy's subtree. Of course, she is greedy, and so she wishes to choose ~K~ pieces of candy such that the sum of the tastiness values of all the candy she eats is maximized. If she chooses a piece of candy, and there is a piece of candy with a negative tastiness below it, she will be forced to eat it :(.

Given the tree and the value ~K~, can you determine the maximum sum of the tastiness values of the candies she eats?

Input Specification

The first line will contain two integers ~N, K~ ~(1 \le K \le N \le 3000)~, the number of pieces of candy, and the special value ~K~.

The next line will contain ~N~ integers, ~t_i~ ~(|t_i| \le 10^7)~, the ~i^\text{th}~ integer indicating the tastiness value of the ~i^\text{th}~ piece of candy.

The next ~N-1~ lines will each contain two integers, ~a_j, b_j~ ~(1 \le a_j, b_j \le N)~, indicating that candies ~a_j~ and ~b_j~ are connected by a string. It is guaranteed that all the pieces of candy are connected.

Output Specification

Output the maximum sum of the tastiness values of the candies Emili can eat.

Subtasks

Subtask 1 [8%]

~N \le 20, |t_i| \le 1~

Subtask 2 [13%]

~N \le 20~

Subtask 3 [26%]

~N \le 300~

Subtask 4 [53%]

No additional constraints.

Sample Input 1

3 2
-1 1 1
1 2
1 3

Sample Output 1

2

Explanation For Sample 1

She can take candies ~2~ and ~3~, along with all the candies below it (none). This gives a sum of ~2~, which is the maximum. If she took candies ~1~, and all of the candies below it ~(2, 3)~, she would only have a sum of ~1~. The tree is drawn below, and the taken candies are highlighted in green.

Sample Input 2

4 1
-1 1 1 1
1 2
1 3
1 4

Sample Output 2

2

Explanation For Sample 2

Sometimes it may be better for Emili to take a negative tastiness candy for the extra sum of the other tastiness!

Sample Input 3

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

Sample Output 3

14

Explanation For Sample 3

It is optimal for Emili to take candies ~3, 5, 6~, along with all the candies below it ~(2)~, for a total sum of ~14~. This is shown in the tree below. The candies Emili takes directly are in green, and the candies she takes as a result are shown in blue.