Задача Q. Клейкая лента ≡

Условие

После женитьбы я стал редко видеть Шерлока Холмса. Мы с супругой поселились в Паддингтоне, где я купил врачебную практику, к сожалению, не приносящую стабильного дохода. Дни шли спокойно и чинно, пламя любви озаряло их таинственным светом.

Однажды в нашу дверь постучали. Решив, что кому-то из соседей потребовалась медицинская помощь, я поспешил вниз. Однако посетитель был мне незнаком. Учтиво приподняв котелок и уточнив, что перед ним стоит именно доктор Джон Ватсон, молодой человек попросил уделить ему несколько минут наедине. На меня нахлынула волна ностальгии, Бог его знает, сколько раз к нам с Холмсом приходили чужие люди с самыми разными просьбами... Интересно, смогу ли я, как мой друг, определить род занятий своего визитера?

Одет небогато, но опрятно, гладко выбрит и аккуратно подстрижен. Речь выдает иностранца, скорее немца. В руке небольшой докторский саквояж, но нет, назвать его доктором я бы не осмелился. После стольких лет практики своих коллег начинаешь узнавать издалека, сразу и без ошибок. Да и на пациента не похож, не выглядит ни больным, ни встревоженным. Что еще? Приехал издалека, из кармана торчит железнодорожный билет, видимо сегодня же уедет обратно. Ко мне с визитом пришел не к первому, лондонский поезд (а откуда еще мог приехать посетитель) прибыл ранним утром. Да и крошки на усах — уже успел у кого-то позавтракать. Умеет расположить к себе, учтив и воспитан.

 —Вижу, Вы гадаете, кто же я такой?  — улыбнулся молодой человек, открыв саквояж, откуда мгновенно появились бумажные упаковки.  —Не буду скрывать, я — коммивояжер, представляю фирму "Beiersdorf". Мы хотим познакомить Вас с интересным изобретением, клейкой лентой с лекарственным антибактериальным покрытием. Ваши коллеги прозвали его лейкопластырем. С его помощью можно зафиксировать края небольшой раны, чтобы избежать заражения крови, также им можно ...

 —Джеймс, скорее!  — в комнату ворвалась жена. Понятия не имею, почему с глазу на глаз она зовет меня другим именем.  —Кэйт чистила рыбу и сильно поранила руку, глубокий порез около 10 дюймов. Сделай что нибудь! Ой, простите, я не знала, что у тебя посетитель...

 —Вот и случай проверить в деле наш чудо-пластырь!  — воскликнул тот.  — У меня с собой два вида упаковки: в одной ленты длиной a дюймов и стоимостью x шиллингов каждая, во второй ленты длиной b дюймов и стоимостью y шиллингов за штуку. Если результат Вас удовлетворит, наша фирма готова высылать по почте любое необходимое количество этой лекарственной формы. Постоянным клиентам скидка!

Помогите доктору Ватсону определить минимальную сумму для приобретения лейкопластырей достаточной суммарной длины для лечения пореза на руке служанки. Считайте, что у коммивояжера неограниченное количество пластырей каждого вида.

Формат входных данных

Первая строка входного файла содержит два натуральных числа, записанных через пробел: a и x — длину и стоимость лейкопластыря первого типа. Вторая строка входного файла содержит два натуральных числа, записанных через пробел: b и y — длину и стоимость лейкопластыря второго типа. В третьей строке содержится одно натуральное число c — длина пореза.

Формат выходных данных

Выведите одно натуральное число — минимальную стоимость, необходимую для приобретения лейкопластырей достаточной суммарной длины. При лечении лейкопластыри можно соединять как встык, так и накладывая их друг на друга. Края лейкопластыря могут выходить за пределы пореза.

Ограничения

1 ≤ a, b, x, y ≤ 100

1 ≤ c ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при a = b, получат не менее 20 баллов.

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

В примере дано два типа лейкопластырей: первый длиной 3 дюйма и стоимостью 2 шиллинга за штуку, второй длиной 4 дюйма и стоимостью 3 шиллинга за штуку. Порез у Кэйт имеет длину 10 дюймов.

Доктору выгоднее потратить два лейкопластыря первого типа и один — второго. Суммарная длина составит 3 + 3 + 4 = 10 дюймов (достаточно для оказания первой помощи), а стоимость — всего 2 + 2 + 3 = 7 шиллингов.

Примеры тестов

3 2
4 3
10

7