AT_past19_k 隣接禁止

There is an $ N $ -vertex tree whose vertices are numbered $ 1 $ through $ N $ . The $ i $ -th edge connects vertex $ u_i $ and vertex $ v_i $ bidirectionally. Vertex $ i $ has an integer $ A_i $ written on it. Determine if there is a way to choose $ K $ vertices among the $ N $ so that no pair of chosen vertices are adjacent. If there is, find the maximum sum of integers written on the chosen $ K $ vertices.

The input is given from Standard Input in the following format: > $ N $ $ K $ $ u_1 $ $ v_1 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $ $ A_1 $ $ \ldots $ $ A_N $

Print `-1` if there is no conforming choice. If there is, print the maximum sum of the integers written on chosen $ K $ vertices.

### Sample Explanation 1 It is optimal to choose vertex $ 3 $ and vertex $ 5 $ . ### Sample Explanation 3 There is no conforming choice. ### Constraints - $ 2\leq N\leq 100 $ - $ 1\leq K \leq N $ - $ 1\leq u_i,v_i\leq N $ - $ 1\leq A_i \leq 100 $ - The input graph is a tree. - All input values are integers.