В королевстве Олимпия находится N городов и M двусторонних дорог, каждая из которых соединяет ровно два города. Между двумя городами может быть более одной дороги. Дорога может соединять город с самим собой, образуя петлю.
Все дороги постоянно грабятся разбойниками. В последнее время разбойникам надоело тратить силы на грабеж и они обратились к могущественному и справедливому королю Олимпии с коммерческим предложением. Согласно этому предложению король должен отправить разбойникам подарок, состоящий из золотых и серебряных монет. В ответ на любезность короля разбойники прекратят грабить определенные дороги. Для каждой из дорог установлено: gi — минимальное количество золотых и si — минимальное количество серебряных монет в подарке, чтобы ее грабеж закончился. То есть, если в подарке a золотых и b серебряных монет, то прекращается грабеж всех дорог, для которых gi ≤ a и si ≤ b.
В казне короля нет ни одной золотой или серебряной монеты, но есть Олимпийские Тугрики. Цена одной золотой монеты в тугриках — G, а серебряной — S. Король хочет, чтобы после отправки подарка разбойникам между каждой парой городов существовал хотя бы один безопасный путь, который, возможно, проходит через другие города. Ваше задание найти минимальное количество тугриков, которую нужно потратить королю для того, чтобы получить безопасные пути между каждой парой городов в королевстве.
Первая строка входных данных содержит два целых числа N и М (2 ≤ N ≤ 200, 1 ≤ M ≤ 50 000) — количество городов и количество дорог в королевстве Олимпия. Вторая строка содержит числа G и S (1 ≤ G, S ≤ 109). Последующие М строк содержат информацию о дорогах и описание предложения разбойников. В і + 2-ой строке входного файла находится четыре натуральных числа xi, yi, ai, bi, где xi и yi — номера городов, которые соединены і-ой дорогой (города нумеруются от 1 до N), а ai, bi — минимальное количество золотых и минимальное количество серебряных монет, которое нужно выслать разбойникам в подарке, чтобы і-ую дорогу прекратили грабить (1 ≤ xi, yi ≤ n, 1 ≤ gi, si ≤ 109).
Единственная строка должна содержать минимальное количество тугриков, которое нужно потратить королю на покупку золотых и серебряных монет, чтобы достичь своей цели. Выведите 
, в случае, если никакое количество тугриков не поможет.
3 3
2 1
1 2 10 15
1 2 4 20
1 3 5 1
30
