Optimal Treasure Observation in a Tree

Eden has obtained a treasure map which represents an undirected connected graph with \(n\) nodes and \(n-1\) edges of length 1, i.e., a tree. Each node \(i\) is labeled with a treasure amount \(w_i\).

Since the treasures are too abundant to be moved all at once, Eden buys \(k\) cameras. Each camera can observe all nodes within a distance \(r\) (the distance between any two nodes in the tree is defined as the length of the shortest path between them). Eden will deploy cameras on at most \(k\) nodes in the tree so that any node within a distance \(\le r\) from a camera is observed.

Your task is to determine the maximum sum of treasure values \(w_i\) from the observed nodes, given the optimal placement of cameras.

inputFormat

The first line contains three integers \(n\), \(k\) and \(r\) (with constraints such as \(1 \le n \le N_{max}\), \(0 \le k \le n\), and \(0 \le r\)).

The second line contains \(n\) integers: \(w_1, w_2, \ldots, w_n\) representing the treasure amounts at each node.

Each of the following \(n-1\) lines contains two integers \(u\) and \(v\) (1-indexed), denoting an undirected edge between nodes \(u\) and \(v\).

outputFormat

Output a single integer representing the maximum sum of treasure amounts that can be observed by optimally placing up to \(k\) cameras.

sample

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

15