Ants and the Anteater

Ants in search of food have come to a mountain that is modeled as a tree with \(n\) caves and \(n-1\) roads connecting them. Each cave is represented as a vertex and every cave with only one connecting road (a leaf) has an exit to the outside. At each exit there are \(g\) groups of ants waiting, where the \(i\)th group has \(m_i\) ants.

The ant groups enter the mountain one after another. A new group enters only when the mountain is empty of ants.

When an ant group enters the mountain (via an exit) it first traverses the unique road connected to that exit. Then, upon arriving at a cave, suppose the cave has \(d\) other roads (excluding the road they just came from). If \(d>0\) the group splits into \(d\) smaller groups, each of size \(\left\lfloor \frac{x}{d} \right\rfloor\), where \(x\) is the number of ants in the arriving group. The remaining ants disappear. Each of the \(d\) groups then continues along one of the \(d\) roads. If \(d=0\) the cave is an exit; in this case, the ants leave the mountain immediately.

On one specific road there is an anteater. Whenever an ant group traveling along that road has exactly \(k\) ants, the anteater eats the entire group (i.e. all \(k\) ants).

Your task is to simulate this process and determine the total number of ants eaten by the anteater.

Input Format: The first line contains four integers \(n\), \(g\), \(k\) and \(r\) where \(n\) is the number of caves, \(g\) is the number of ant groups at each exit, \(k\) is the critical number of ants that triggers the anteater, and \(r\) (1-indexed) is the index of the road that has the anteater. The next \(n-1\) lines each contain two integers \(u\) and \(v\) indicating that there is a road connecting caves \(u\) and \(v\). The last line contains \(g\) integers \(m_1, m_2, \ldots, m_g\), the sizes of the ant groups waiting at every exit.

Note: For each exit (a leaf in the tree), the ant group begins by traveling along its only incident road. Every time an ant group travels along a road, if that road is the designated special road and the group size is exactly \(k\), then the anteater eats the entire group and the propagation along that road stops.

inputFormat

The first line contains four integers: \(n\), \(g\), \(k\), and \(r\).
The next \(n-1\) lines each contain two integers \(u\) and \(v\), representing a road between caves \(u\) and \(v\).
The last line contains \(g\) integers: \(m_1, m_2, \ldots, m_g\).

outputFormat

Output a single integer representing the total number of ants eaten by the anteater.

sample

2 2 3 1
1 2
3 4

6