CC: Взрываем муниципальный этап

В Москве начал работать новый оператор сотовой связи, предоставляющий доступ в интернет посредством технологии 7G. Новый оператор предлагает простые и невысокие тарифы, в частности, один мегабайт интернет-трафика стоит 1 рубль.

Кроме того, оператор предлагает покупать оптовые пакеты трафика – есть два предложения: купить пакет трафика на \(A\) мегабайт за \(B\) рублей и купить пакет трафика на \(C\) мегабайт за \(D\) рублей.

Таня планирует использовать в течение месяца \(N\) мегабайт интернет-трафика. Определите минимальную сумму, которую придётся ей заплатить. Таня может приобретать любое количество каждых из двух предлагаемых пакетов, а также оплачивать трафик по тарифу «1 рубль за мегабайт». Таня может приобретать пакеты интернет-трафика и в том случае, если суммарный оплаченный трафик будет более \(N\) мегабайт, если это выйдет дешевле.

Программа получает на вход пять натуральных чисел \(N\), \(A\), \(B\), \(C\), \(D\), записанных в отдельных строках, не превосходящих \(500.000\) каждое. Гарантируется, что \(A > B\) и \(C > D\). Программа должна вывести одно целое число – минимальную сумму, которую нужно заплатить для приобретения \(N\) мегабайт трафика.

Пояснение к первому примеру

Пакет на 10 мегабайт стоит 9 рублей, пакет на 20 мегабайт стоит 17 рублей. Для оплаты 35 мегабайт нужно купить пакет на 10 мегабайт и пакет на 20 мегабайт, а за оставшиеся 5 мегабайт заплатить 5 рублей.

Пояснение ко второму примеру

35
10
9
20
17

31

55
30
20
20
16

40