e-olymp
Задачі

Паливо

Паливо

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

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

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

Вхідні дані

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

Вихідні дані

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #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
Вихідні дані #10
102
Автор В.Л.Дідковський
Джерело III етеп Всеукраїнської олімпіади з інформатики в Житомирській обл. 2007-2008 р