Lamps and batteries P28695

A certain castle consists of $n$ rooms connected by corridors that form a tree. Every room is illuminated by several wall lamps. Every lamp works with one huge battery. Batteries are identical and so heavy that only one can be carried at a time.

A recent visitor of the castle removed the batteries from all lamps, and moved some of them to different rooms. Suppose that it takes $e$ seconds to traverse a corridor without carrying any battery, $c$ seconds carrying one, and $i$ seconds to install a battery into a lamp located in the same room. What is the minimum time to install one battery into every lamp? You must start and finish in the reception room of the castle.

Input

Input consists of several cases. Every case begins with $n$, $e$, $c$ and $i$, followed by $n-1$ pairs of rooms describing the corridors, followed by $n$ pairs of numbers describing the amount of lamps and batteries inside each room. Assume $1 \le n \le 10^4$, $e \le c$, that $e$, $c$ and $i$ are between 1 and 100, and that there are no more than 100 lamps or batteries inside each room. Rooms are numbered from 0 to $n-1$. The reception room is number 0. The total number of lamps equals the total number of batteries.

Output

For every case, print the optimum time to install one battery into every lamp. The test cases are such that the result is never larger than $10^9$.