N котелень однакової потужності сполучені системою трубопроводів з М труб для перекачки палива. На 9.00 ранку виявилось, що фактичні запаси палива Ak т (k=1..N) такі, що в одній з котелень його значно менше норми В т, а на інших – вдосталь або більше норми.

Сумарні запаси палива дозволяють виправити ситуацію, якщо перерозподілити паливо. У кожний момент часу з N насосів можуть працювати 0 або 2 (в сусідніх котельнях, що перекачують та приймають паливо), при цьому перекачка 1 т палива на 1 км займає С хв.

Через який найменший час T хв ця робота буде виконана?

Вхідні дані

В першому рядку задані 4 числа N, M, B, C. У другому - масив значень A[1..N]. Далі йде M рядків - пари номерів котелень та довжини труб між ними. Всі дані – невід’ємні цілі числа, не більші 50.

Вихідні дані

Єдине число - шуканий час.