Задача D. Вагон и маленькая тележка ≡

Условие

В последние годы наблюдается значительный рост использования роботов в различных отраслях. Технологии искусственного интеллекта и автоматизации позволяют им работать без участия человека, что повышает эффективность и безопасность самых разных процессов, в частности складской логистики. Это приводит к увеличению производительности, снижению затрат на персонал и сокращению риска возникновения человеческих ошибок.

Прогресс добрался и до небольшой железнодорожной станции "Ту-тульская". Грузчику Феде наконец-то выделили помощника — беспилотную тележку, способную самостоятельно доставлять ящики и коробки из вагона на склад. Пока эксперимент по внедрению чудо-машины не завершен, Федя и робот работают вместе.

В прибывшем почтовом вагоне находятся грузы двух видов: p посылок и k контейнеров. Федя способен переместить одну посылку из вагона на склад за a минут, а один контейнер — за b минут. Тележка перемещает одну единицу любого груза за c минут. Определите наименьшее количество времени, за которое человек и робот разгрузят вагон.

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

Единственная строка входных данных содержит натуральное число n.

Пять строк входных данных содержат целые числа p, k, a, b и c.

Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

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

Выведите одно неотрицательное целое число — ответ на вопрос задачи. Гарантируется, что ответ не превысит 10¹⁸.

Ограничения

0 ≤ p, k ≤ 10⁹

1 ≤ a < b ≤ 10⁹

1 ≤ c ≤ 10⁹

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

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

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

Решения, верно работающие при p + k ≤ 100, получат не менее 30 баллов.

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

В примере дано: в вагоне 10 посылок и 15 контейнеров. Федя переносит одну посылку за 2 минуты, один контейнер за 5 минут, робот переносит любой груз за 3 минуты. Как видно, выгоднее, чтобы человек перенес посылки, а робот — контейнеры. За 20 минут Федя перенесёт все посылки, а робот — 6 контейнеров (и уже будет переносить седьмой). Дальше грузчики совместно за 16 минут вынесут из вагона все контейнеры. Всего Федя перенесёт 10 посылок и 3 контейнера, а робот — 12 контейнеров.

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

10
15
2
5
3

36