Топливо
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.
Выходные данные
Единственное число - искомое время.