Description

In front of the fugitive there is a maze. The maze consists of $n$ rooms and $n-1$ bidirectional corridors. Each corridor connects two different rooms, and all rooms are reachable from each other through the corridors. In other words, it is a tree.

The fugitive will choose a room to enter the maze, walk through some corridors, and then leave the maze, but he will never walk through the same corridor twice.

In room $i$, there are $F_i$ iron balls. Whenever someone passes through this room, they will be blocked by the iron balls. The fugitive has $V$ magnets. When he arrives at a room, he may choose to drop one magnet (or not). This will pull all iron balls from every room adjacent to this room into this room. The process is as follows:

1. The fugitive enters the room.
2. The fugitive drops a magnet.
3. The fugitive leaves the room.
4. The iron balls are pulled into this room.

Note that the fugitive is only blocked by the iron balls originally in this room, and will not be blocked by the iron balls pulled into this room.

After the fugitive leaves the maze, the pursuer will go through the maze along the path taken by the fugitive, and he will encounter all iron balls on this path.

Please help the fugitive choose a path to maximize: (number of iron balls encountered by the pursuer) minus (number of iron balls encountered by the fugitive).

Input Format

The first line contains two space-separated integers $n$ and $V$.

The second line contains $n$ space-separated integers representing $F_i$.

Then follow $n-1$ lines. Each line contains two space-separated integers $x$ and $y$, indicating that there is a corridor connecting room $x$ and room $y$.

Output Format

Output one integer, representing the maximum possible value of (number of iron balls encountered by the pursuer) minus (number of iron balls encountered by the fugitive) in the optimal case.

12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12

36

Hint

Sample Explanation

One optimal plan is as follows:

• Enter the maze from room $6$ and drop the first magnet. He encounters $5$ iron balls. At this time, room $6$ will have $27$ iron balls, while rooms $5$, $7$, $8$, and $9$ will have no iron balls.
• Walk to room $7$, drop the second magnet, and leave the maze. He encounters $0$ iron balls. At this time, room $7$ will have $41$ iron balls, while rooms $2$, $4$, $6$, and $10$ will have no iron balls.

In this process, the fugitive encounters $5$ iron balls, while the pursuer encounters $41$ iron balls.

Constraints

For $100\%$ of the testdata, $1\le n\le 10^5;0\le V\le 100;0\le F_i\le 10^9$​​。

Translated by ChatGPT 5