# The Fuel

# The Fuel

**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:**

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.

5 5 4 6 5 4 8 1 6 1 2 3 2 3 5 2 4 2 3 4 6 3 5 4

102