Задача №111762. Подарок
В королевстве Олимпия находится 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, в случае, если никакое количество тугриков не поможет.
1 ≤ m ≤ 150. Решение оценивается в 25 баллов.
1 ≤ m ≤ 4 000. Решение оценивается в 25 баллов.
Дополнительные ограничения отсутствуют. Решение оценивается в 50 баллов.
3 3 2 1 1 2 10 15 1 2 4 20 1 3 5 1
30