Подарунок#2007
Королівство Олімпія складається з міст і двосторонніх доріг. Кожна дорога з'єднує рівно два міста, і між двома містами може бути більше однієї дороги. Також можливо, що дорога з'єднує місто саме з собою, утворюючи петлю.
Усі дороги постійно грабуються розбійниками. Згодом розбійники втомилися від пограбувань та запропонували королю Олімпії надіслати їм подарунок з золотих та срібних монет. Для кожної дороги визначені g_i — мінімальна кількість золотих монет і s_i — мінімальна кількість срібних монет у подарунку для припинення грабежу цієї дороги. Тобто, якщо у подарунку золотих і срібних монет, то грабування припиняється на всіх дорогах, для яких g_i \leq a і s_i \leq b.
У скарбниці немає ані золотої, ані срібної монети, але є Олімпійські тугрики. Ціна однієї золотої монети — тугриків, а однієї срібної — тугриків. Король хоче надіслати такий подарунок, щоб між кожною парою міст існував хоча б один безпечний шлях.
Ваше завдання — за інформацією про міста, дороги та ціни монет знайти мінімальну кількість тугриків, потрібну для такого подарунку.
Перший рядок містить два цілих числа і (2 \leq N \leq 200, 1 \leq M \leq 50\,000) — кількість міст і доріг відповідно.
Другий рядок містить два числа і (1 \leq G, S \leq 10^9) — ціни золотої і срібної монети у тугриках.
Далі йдуть рядків по чотири цілих числа x_i, y_i, g_i, s_i — x_i і y_i — номери міст, які з'єднує -та дорога (1 \leq x_i, y_i \leq N), g_i і s_i (1 \leq g_i, s_i \leq 10^9) — мінімальні вимоги до кількості монет для припинення грабежу -тої дороги.
Міста нумеруються з до . Між парою міст може бути кілька доріг. Можливі дороги з міста у себе.
Виведіть одне ціле число — мінімальну кількість тугриків, яку потрібно витратити на купівлю монет, або , якщо це неможливо за будь-якої кількості тугриків.
Приклад 1