Tree Points

You are given an undirected tree rooted at node 0 and a positive integer A[u] for each node. Starting from the root, a node can be processed only after its parent has been collected. When processing a node, you can either collect its current value minus K points, or collect its current value integer-divided by 2 points and integer-divide by 2 the values of that node and of every unprocessed node in its whole subtree. A single step may have a negative gain. Maximize the total points.

The standard input/output, the ranges added by this site, and the examples follow this problem's description.

输入格式

The first line contains n K (1≤n≤100000, 1≤K≤10^9); the second line contains n values A[u] (1≤A[u]≤10^9); the next n−1 lines are 0-based undirected edges u v. The remaining tree constraints are taken from the original problem.

输出格式

Output the maximum total points obtainable, using 64-bit integers.

样例 1

输入：

4 5
10 10 3 3
0 1
1 2
2 3

输出：

11

样例 2

输入：

1 5
3

输出：

1

样例 3

输入：

3 3
8 4 2
0 1
1 2

输出：

7