В королевстве Олимпия находится N городов и M двусторонних дорог, каждая из которых соединяет ровно два города. Между двумя городами может быть более одной дороги. Дорога может соединять город с самим собой, образуя петлю.
Все дороги постоянно грабятся разбойниками. В последнее время разбойникам надоело тратить силы на грабеж и они обратились к могущественному и справедливому королю Олимпии с коммерческим предложением. Согласно этому предложению король должен отправить разбойникам подарок, состоящий из золотых и серебряных монет. В ответ на любезность короля разбойники прекратят грабить определенные дороги. Для каждой из дорог установлено: gi — минимальное количество золотых и si — минимальное количество серебряных монет в подарке, чтобы ее грабеж закончился. То есть, если в подарке a золотых и b серебряных монет, то прекращается грабеж всех дорог, для которых gi ≤ a и si ≤ b.
В казне короля нет ни одной золотой или серебряной монеты, но есть Олимпийские Тугрики. Цена одной золотой монеты в тугриках — G, а серебряной — S. Король хочет, чтобы после отправки подарка разбойникам между каждой парой городов существовал хотя бы один безопасный путь, который, возможно, проходит через другие города. Ваше задание найти минимальное количество тугриков, которую нужно потратить королю для того, чтобы получить безопасные пути между каждой парой городов в королевстве.
Выходные данные
Единственная строка должна содержать минимальное количество тугриков, которое нужно потратить королю на покупку золотых и серебряных монет, чтобы достичь своей цели. Выведите 
, в случае, если никакое количество тугриков не поможет.