You are given a tree of n vertices rooted at 1, vertex i has the number Ai on it.
Find the maximum possible sum of all vertices can be obtained by removing at most k subtrees.
### Input
- The first line contain 2 integers n,k.
- The second line contains n integers Ai.
- The next n−1 lines, each line contains 2 integers u and v, there is an edge between u and v.
### Output
- Print the maximum sum.
### Constraints
- 1≤n≤105.
- 1≤k≤100.
- 1≤u,v≤n.
- 0≤|Ai|≤109.
### Example
Input:
74223−4−504122314252657
Output:
7