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

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

   Через какое наименьшее время T минут эта работа будет выполнена?

   Входные данные

   В первой строке заданы 4 числа N, M, B, C. Во второй - массив значений A[1..N]. Далее идут M строк - пары номеров котелен и длины труб между ними. Все данные - неотрицательные целые числа, не превышающие 50.

   Выходные данные

   Единственное число - искомое время.