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
