Minimizing Equipment Purchase Cost under Subtree Constraints

You are given a tree with N rental points (nodes). Each rental point has a cost per equipment set. In addition, for each rental point i a marketing team has provided a range \([L_i, R_i]\) that specifies the acceptable total number of equipment sets purchased in the subtree rooted at i (including i itself).

Your task is to determine a nonnegative integer purchase \(x_i\) for each rental point i such that for every node i, if \(S_i = x_i + \sum_{j \in \text{subtree of } i} x_j\) then \[ L_i \le S_i \le R_i, \] and the total cost \[ \text{Cost} = \sum_{i=1}^{N} c_i \times x_i \] is minimized. If no valid assignment exists, output -1.

Input Format: The first line contains an integer N denoting the number of rental points. The next N-1 lines each contain two integers u and v representing an edge between nodes u and v. The following line contains N integers, where the i-th integer is the cost \(c_i\) per equipment set at node i. Then N lines follow; the i-th of these lines contains two integers \(L_i\) and \(R_i\), the lower and upper bounds for the total equipment sets in the subtree rooted at i respectively.

Output Format: Output a single integer: the minimum total cost to satisfy all the conditions, or -1 if it is impossible.

inputFormat

The input begins with a single integer N (the number of nodes).

Then follow N-1 lines, each containing two space-separated integers u and v (1-indexed) describing an edge of the tree.

Next, a line with N space-separated integers: c1, c2, ..., cN representing the cost per equipment set at each node.

Finally, N lines follow. The i-th line contains two space-separated integers, L_i and R_i, representing the lower and upper bound respectively for the sum of equipment sets in the subtree rooted at node i.

outputFormat

Print a single integer representing the minimum total cost to purchase equipment sets meeting the constraints, or -1 if no valid assignment exists.

sample

3
1 2
1 3
3 2 1
5 10
2 4
1 2

11