e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

The Fuel

The Fuel

prb45N boiler rooms of identical power is connected by the system of pipelines with M of pipes for a transfer of fuel. At 9.00 a.m. we saw that actual block of A[k] of t (k=1..N) fuels are such, that in one of boiler rooms is far fewer norm B tone and for others are in plenty or more than norm.

If redistribute a fuel total block fuels allow to correct a situation. In every moment time from N of pumps can work 0 or 2 pumps (in neighbors boiler rooms which pump over and accept a fuel), here the transfer of 1 tons fuel to a 1 km occupies C minutes. What the least time of T minutes this work will be execute?

Input:

In the first line is 4 numbers N, M, B, C. In the second line is array A[1..N]. There are M lines with pair numbers of the boiler rooms and length of the pipe between them. All information are inalienable integers, not greater 50.

Output

One number - the time.

Time limit 1 second
Memory limit 64 MiB
Input example #10
5   5   4   6 
5  4  8  1  6
1  2  3
2  3  5
2  4  2
3  4  6
3  5  4
Output example #10
102