Топливо - Задачи

N котелен одинаковой мощности соединены системой трубопроводов из M труб для перекачки топлива. На 09:00 утра оказалось, что фактические запасы топлива A_k тонн (k = 1..N) таковы, что в одной из котелен его значительно меньше нормы B тонн, а на остальных - достаточно, либо с избытком.

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

Через какое наименьшее время 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