Подарунок
У королівстві Олімпія знаходиться 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, у випадку, якщо жодна кількість тугриків не допоможе.