You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 3.0 s

Memory Limit: 1024.0 MB

Description

You are given a binary tree of \(N\) node rooted at node 1 and an integer \(K\). Each node \(i\) has a value \(a_i\) assigned to it.

A path \([a,b]\) is defined as the shortest way to go to node \(b\) from node \(a\). length of the path \([a,b]\) is the number of nodes visited in the path included node \(a\) and \(b\).
Weight of a path is the sum of the values of all nodes included in the path.

Find the maximum weight among all path of length exactly \(K\). if there no such path exist which has a length \(K\), print 0.

a binary tree is a tree in which every node has at max 2 child.

Input

First line takes 2 integer \(N,K\) : number of nodes, length of the path
next line takes \(N\) integers \(a_1,a_2,a_3...a_n\) : \(a_i\) is the value assigned to \(i^{th}\) node
next \(N-1\) line each takes 2 integer \(u,v\) which means there is an edge between node \(u\) and node \(v\)

\(1 <= N <= 10^5\)
\(1 <= K <= 300\)
\(1 <= a_i <= 10^9\)

Output

One integer, the maximum weight among all path of length exactly \(K\)

Sample

6 3
1 5 3 4 1 4
1 2
3 1
2 4
5 2
3 6

10