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?
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.
One number - the time.
5 5 4 6 5 4 8 1 6 1 2 3 2 3 5 2 4 2 3 4 6 3 5 4