In the ancient ruins of the Tomb of the Kings in Paphos, echoes propagate through a network of chambers connected by tunnels. The network is a tree-like structure with $$$n$$$ chambers and $$$n-1$$$ tunnels. The entrance is located at chamber 1.
Each chamber contains an ancient artifact activated by the sound of echo. To activate the artifact in chamber $$$i$$$, the strength of echo in this chamber must be at least $$$d_i$$$.
The strength of the echo is an integer number. It may be both positive or negative. The echo starts at the entrance (chamber 1) with strength 0 and spreads throughout tunnels in the direction from the entrance. Every time the echo moves through a tunnel, its strength decreases by $$$1$$$.
To increase the strength of the echo, you may use special resonators. If you put a resonator in some chamber, the strength of echo in this room will be increased by one. This amplified echo will then be moving forward to further chambers, so as a result, the strength of the echo in all reachable chambers will be increased by one.
 |  |
| Echo strength without resonators | Echo strength with one resonator in chamber 4 |
You can put at most $$$F$$$ resonators in each chamber.
Your task is to find the minimal number of resonators needed to activate all the artifacts.
The first line of the input contains integers $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) and $$$F$$$ ($$$0 \le F \le 2 \cdot 10^9$$$).
The second line contains $$$n$$$ integers $$$d_1 \ldots d_n$$$ ($$$|d_i| \le 10^9$$$).
The next $$$n-1$$$ lines each contain two integers $$$u$$$, $$$v$$$ meaning that a tunnel exists between chambers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$).
Output one integer: the minimal number of resonators needed to make the echo strength reaching each chamber $$$i$$$ at least $$$d_i$$$.
If it is impossible to activate all the artifacts, output $$$-1$$$.
This task contains four subtasks. To get the points for the subtask, your solution should pass all the tests in the corresponding subtask.
| Subtask | Constraints | Points |
| $$$1$$$ | $$$n \le 8$$$, $$$F \leq 5$$$ | $$$12$$$ |
| $$$2$$$ | For each $$$i$$$ from 1 to $$$n-1$$$, nodes $$$i$$$ and $$$i+1$$$ are connected with a tunnel | $$$25$$$ |
| $$$3$$$ | $$$F = 2 \cdot 10^9$$$ | $$$13$$$ |
| $$$4$$$ | $$$F = 0$$$. | $$$9$$$ |
| $$$5$$$ | $$$n \le 1000$$$ | $$$16$$$ |
| $$$6$$$ | No additional constraints | $$$25$$$ |
6 22 -1 0 2 0 11 41 52 44 33 6
4
2 01000000000 -11 2
-1
5 3-2 1 5 3 24 13 54 23 1
7
Here is an illustration for the first example.
