409486: GYM103577 L Convert to heap

You have a tree with $$$n$$$ vertices ($$$1 \leq n \leq 10^5$$$), numbered from $$$1$$$ to $$$n$$$ and rooted at node $$$1$$$. Every node $$$i$$$ has an integer value $$$a_i$$$ ($$$0 \leq a_i \leq 10^9$$$).

You can update the values of the nodes $$$q$$$ times ($$$1 \leq q \leq 1000$$$). In the $$$i$$$-th update, you can choose a subset of nodes and increase the value of all of them by $$$x_i$$$ ($$$1 \leq x_i \leq 1000$$$).

You task is to use these updates to convert the tree into a heap. The tree is considered a heap if and only if every non-root node has a value less than or equal to the value of its parent. Since there can be multiple ways to do this, you must choose the one that minimizes $$$\sum_{i=1}^n a_i$$$.

The first line of input contains two space separated integers: $$$n$$$ and $$$q$$$.

The second line contains $$$n$$$ space separated integers: $$$a_i$$$.

Each of the next $$$n-1$$$ lines describe the edges of the tree, each contains two space separated integers: $$$u$$$ and $$$v$$$ (Meaning there is an edge between $$$u$$$ and $$$v$$$).

The next and final line of input contains $$$q$$$ space separated integers: $$$x_i$$$.

If there is a way to convert the tree into a heap, output the minimum $$$\sum_{i=1}^n a_i$$$ after converting it to a heap. Otherwise output -1.

5 2
40 20 20 20 50
1 2
2 3
2 4
3 5
10 20

220

5 2
40 20 20 20 51
1 2
2 3
2 4
3 5
10 20

-1