J. Skill Tree
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In the game that Xiaoqiang plays, there is a skill tree system.

The skill tree is a tree with node $$$1$$$ as the root node, where each node on the tree represents a skill. Xiaoqiang can use gold coins to light up skills on the skill tree to gain combat power. The prerequisite for lighting up a skill is that the skill's parent node must be lit up. In particular, the root node can be lit up directly.

Each skill has a combat power value, and the combat power gained by Xiaoqiang for lighting up a skill is calculated as follows:

  1. Sort the combat power values of all skills on the path from the root node to that skill (including the root node and that skill) in ascending order.
  2. After sorting, the $$$ \lfloor \frac{x}{2} \rfloor + 1 $$$-th smallest combat power value is the combat power gained by Xiaoqiang for lighting up that skill (where $$$x$$$ is the number of skills on the path from the root node to that skill).

At the same time, Xiaoqiang needs one gold coin to light up a skill, and skills cannot be lit up more than once. Xiaoqiang does not have to use all $$$m$$$ gold coins.

Xiaoqiang currently has $$$m$$$ gold coins, and he hopes to maximize his combat power with these $$$m$$$ coins.

  • $$$\lfloor x \rfloor$$$ denotes the largest integer not exceeding $$$x$$$, for example, $$$\lfloor 4 \rfloor = 4$$$, $$$\lfloor 1.2 \rfloor = 1$$$, $$$\lfloor -2.5 \rfloor = -3$$$.
Input

First, input a line with two integers $$$n, m(1 \le n \le 2 \times 10^4, 1 \le m \le 2 \times 10^3)$$$, representing the number of skills on the skill tree and the number of gold coins Xiaoqiang has.

Next, input a line with $$$n$$$ integers, $$$v_1, v_2, \dots, v_n(0 \le v_i \le 1\times 10^9)$$$, where $$$v_i$$$ represents the combat power value of the skill with index $$$i$$$.

Then, input $$$n - 1$$$ lines, each containing two integers $$$u, v(1 \le u, v \le n)$$$, indicating that there is an edge between the skill with index $$$u$$$ and the skill with index $$$v$$$.

Output

Output a single integer, representing the maximum combat power that Xiaoqiang can obtain.

Examples
Input
5 3
1 2 3 4 5
1 2
1 3
2 4
2 5
Output
6
Input
5 5
1 2 3 4 5
1 2
2 3
3 4
4 5
Output
11
Input
5 3
1 2 3 4 5
1 2
2 3
3 4
4 5
Output
5
Note

In the first sample, Xiaoqiang can choose to light up the skills with indices $$$1$$$, $$$2$$$, and $$$3$$$.

In the second sample, Xiaoqiang can obtain all skills. After lighting up the skill with index $$$1$$$, he can gain $$$1$$$ unit of combat power; after lighting up the skills with indices $$$2$$$ and $$$3$$$, he can gain $$$2$$$ units of combat power; after lighting up the skills with indices $$$4$$$ and $$$5$$$, he can gain $$$3$$$ units of combat power.