Подарок
В королевстве Олимпия находится N городов и M двусторонних дорог, каждая из которых соединяет ровно два города. Между двумя городами может быть более одной дороги. Все дороги постоянно грабятся разбойниками. В последнее время разбойникам надоело тратить силы на грабеж и они обратились к могущественному и справедливому королю Олимпии с коммерческим предложением. Согласно этому предложению король должен отправить разбойникам подарок, состоящий из золотых и серебряных монет. В ответ на любезность короля разбойники прекратят грабить определенные дороги. Для каждой из дорог установлено минимальное количество золотых и минимальное количество серебряных монет в подарке, чтобы ее грабеж закончился. То есть, если в подарке K золотых и L серебряных монет, то прекращается грабеж всех дорог, для которых необходимое количество золотых монет меньше или равно K, а количество серебряных монет меньше или равно L.
В казне короля нет ни одной золотой или серебряной монеты, но есть Олимпийские Тугрики. Цена одной золотой монеты в тугриках – G, а серебряной – S. Король хочет, чтобы после отправки подарка разбойникам между каждой парой городов существовал хотя бы один безопасный путь, который, возможно, проходит через другие города.
Напишите программу, которая по данным о городах и дорогах в королевстве и ценами монет, найдет минимальное количество тугриков, которую нужно потратить королю для того, чтобы получить безопасные пути между каждой парой городов в королевстве.
Входные данные
Первая строка содержит два целых числа N и М (2 ≤ N ≤ 200, 1 ≤ М ≤ 50 000) - количество городов и количество дорог в королевстве Олимпия. Вторая строка содержит числа G и S (1 ≤ G, S ≤ 10^9). Последующие М строк содержат информацию о дорогах и описание предложения разбойников. В і+2-ой входной строке находится 4 натуральних числа, первые два из которых – номера городов, которые соединены і-ой дорогой (города нумеруются от 1 до N), следующие два - минимальное количество золотых и минимальное количество серебряных монет, которое нужно выслать разбойникам в подарке, чтобы і-ую дорогу прекратили грабить. Оба числа не превышают 10^9.
Вывести одно целое число - минимальное количество тугриков, которое нужно потратить королю на покупку золотых и серебряных монет, чтобы достичь своей цели, или -1, в случае, если никакое количество тугриков не поможет.