You are given an edge-weighted tree with vertices labeled through , where each vertex has a value .

You need to select a subset of at most  vertices with distinct values. You want to maximize the sum of weights of "spanned" edges, where an edge is "spanned" if and only if there exists such that lies on the only path between and .

输入描述:

The first line contains two integers , denoting the size of the tree and the maximum size of the subset you need to choose, respectively.

The second line contains  integers , denoting the value of each vertex.

Then  lines follow, where each line contains  integers , denoting there is an edge  with weight  in the tree.

输出描述:

Output an integer in a line, denoting the maximized sum of weights of "spanned" edges.

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

6

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

4

备注:

For the first sample test, you can choose  so that every edge of the tree is "spanned".

For the second sample test, note that since , you cannot choose  even though that would span every edge in the tree. A valid subset that maximizes  the sum of weights of ``spanned'' edges is .