Description

There are $n$ farmers living in $n$ different villages. These $n$ villages form a tree. Initially, each farmer has $x$ dollars.

In one operation, a farmer may take any amount of money from their own money and give it to a farmer in an adjacent village.

For each farmer, a value $v_i$ is given. Find the minimum number of operations needed so that in the end every farmer has money $\ge$ the given value.

Input Format

The first line contains an integer $n$, the number of farmers.

The second line contains an integer $x$, the amount of money each farmer initially has.

The third line contains $n$ integers, where the $i$-th number is $v_i$.

The next $n - 1$ lines each contain two integers, representing an edge of the tree.

Output Format

Output one line with one integer, the minimum number of operations required.

6
15
10 20 18 16 6 16
1 4
4 5
4 6
6 2
5 3

5

Hint

Constraints

For $100\%$ of the testdata, $1 \le n \le 2000$, $0 \le x \le 10000$, $\sum\limits_{i=1}^n v_i \le n \times x$.

Notes

Translated from Croatian Highschool Competitions In Informatics 2009 Final Exam #1 T2 PODJELA。

Translated by ChatGPT 5