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 ≤ *n* ≤ 10^{4},
*e* ≤ *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}.

Public test cases

**Input**

3 30 60 10 0 1 0 2 0 0 1 0 0 1 3 30 60 10 0 1 2 1 1 3 1 0 1 0 3 30 60 10 2 1 1 0 0 0 0 0 1 1 5 30 60 10 0 1 0 2 2 3 2 4 0 0 1 0 1 1 1 2 0 0

**Output**

190 300 130 300

Information

- Author
- Pol Mauri
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Dotzè Concurs de Programació de la UPC - Final
- Date
- 2014-10-01