\includegraphics{https://static.e-olymp.com/content/73/73b125feba7b388918eecf494ae6afae80360d0f.jpg} \textbf{N} boiler rooms of identical power is connected by the system of pipelines with \textbf{M} of pipes for a transfer of fuel. At \textbf{9.00} a.m. we saw that actual block of \textbf{A\[k\]} of \textbf{t} (\textbf{k=1..N}) fuels are such, that in one of boiler rooms is far fewer norm \textbf{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 \textbf{N} of pumps can work \textbf{0} or \textbf{2} pumps (in neighbors boiler rooms which pump over and accept a fuel), here the transfer of \textbf{1} tons fuel to a \textbf{1} km occupies \textbf{C} minutes. What the least time of \textbf{T} minutes this work will be execute? \InputFile In the first line is \textbf{4} numbers \textbf{N}, \textbf{M}, \textbf{B}, \textbf{C}. In the second line is array \textbf{A\[1..N\]}. There are \textbf{M} lines with pair numbers of the boiler rooms and length of the pipe between them. All information are inalienable integers, not greater \textbf{50}. \OutputFile One number - the time.