Ant colony

Ants are searching an abandoned ant hill for food. The hill has $n$ chambers and $n-1$ corridors joining them. Between any two chambers there is exactly one path, so the chambers and the corridors form a tree.

Every chamber with only one corridor attached to it has an entrance. At each entrance there are $g$ groups of ants waiting, of sizes $m_1, m_2, \dots, m_g$. The groups enter one after another, and the next group enters only once no ants are left inside. Inside the hill the ants move like this.

• When a group enters a chamber with $d$ corridors it has not walked through yet, the group splits into $d$ groups of equal size. Each new group follows one of the $d$ corridors. If $d=0$, the group leaves the hill.
• If the group cannot be split into equal parts, the stronger ants eat the weaker ones until the split comes out even. The number of ants can drop all the way to zero, so such a split is always possible. Nothing stops the ants from making the number divisible. An ant can eat itself, and the last one left does so when the group is smaller than $d$.

The picture below shows $m$ ants entering a chamber with three corridors they have not walked through yet, splitting into three groups of $\lfloor m/3 \rfloor$ ants each.

A hungry anteater dug into one of the corridors and can now eat every ant that passes through it. The anteater is as picky about numbers as the ants are: it devours a passing group if and only if the group has exactly $k$ ants. Count how many ants the anteater eats in total.

The first line contains three integers $n$, $g$, $k$ separated by single spaces ($2 \le n, g \le 1{,}000{,}000$, $1 \le k \le 10^9$). They give the number of chambers, the number of ant groups, and the number of ants the anteater devours at once. The chambers are numbered from 1 to $n$.

The second line contains $g$ integers $m_1, m_2, \dots, m_g$ separated by single spaces ($1 \le m_i \le 10^9$), where $m_i$ is the size of the $i$-th group at every entrance.

Each of the next $n-1$ lines describes one corridor. The $i$-th of these lines contains two integers $a_i$ and $b_i$ separated by a single space ($1 \le a_i, b_i \le n$), meaning that chamber $a_i$ and chamber $b_i$ are joined by a corridor. The anteater dug into the corridor that appears first in the input.

Print one line with the number of ants the anteater eats.

In the first example there are 5 groups of ants next to chambers 2, 3, 5 and 7. The anteater eats 3 ants from the first group that starts at chamber 2, and 3 ants from the fourth group and 3 ants from the fifth group starting at each of chambers 3, 5 and 7. The X in the picture marks the corridor the anteater dug into.