Maximizing Army Combat Power with Median Constraints

King L’s country has n cities connected by n − 1 roads forming a tree. The king must station an army on each road. The combat power of an army can be any integer in the range \( [1, m] \). Each city i has a governor with a tolerance value \(a_i\). For every city, consider the list of values on all roads incident to it. Let the median (defined as the \( \left\lfloor \frac{k}{2} \right\rfloor+1 \)-th smallest number among \(k\) numbers) be computed. If the median exceeds the governor’s tolerance, the governor will rebel.

The king wants no rebellion while maximizing the total combat power of the armies. In other words, assign to each road an integer between \(1\) and \(m\) such that for every city \(i\) the median value of the armies on roads incident to city \(i\) does not exceed \(a_i\), and the sum of values over all roads is maximized.

If no valid assignment exists, output \(-1\).

Note: For any \(k\) numbers, when sorted in non‐decreasing order, the median is defined as the \(\left\lfloor\frac{k}{2}\right\rfloor+1\)-th number.

inputFormat

The first line contains two integers \(n\) and \(m\) \((2 \le n \le 2000,\; 1 \le m \le 10^9)\).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) \((1 \le a_i \le m)\) representing the tolerance of each city’s governor.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) \((1 \le u,v \le n, u \ne v)\) representing a road connecting cities \(u\) and \(v\). It is guaranteed that the roads form a tree.

outputFormat

Output a single integer — the maximum possible total combat power if an assignment avoiding any rebellion exists; otherwise, output \(-1\).

sample

3 5
3 5 4
1 2
2 3

7