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