eolymp
bolt
Try our new interface for solving problems
Problems

The Fuel

The Fuel

Time limit 1 second
Memory limit 64 MiB

N 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 data

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 data

One number - the time.

Examples

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