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

Main difference between the easy and hard version is in the easy version the tree is guaranteed to be a binary tree. Also in easy version \(K<=300\) and in hard version \(K<=100\)

You are given a tree of \(N\) node 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.

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 <= 100\)
\(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