Добыча пряности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

На первых этапах Атрейдесам был доступен только один харвестер (комбайн) для сбора, поэтому необходимо было срочно наладить их производство.

  1. Компонент I для харвестера можно произвести за $$$t_1$$$ времени из металлолома, которого в пустыни Арракиса неограниченное количество.
  2. Компонент II производится из уже готового первого компонента за $$$t_2$$$ времени.
  3. Харвестер производится за $$$t_3$$$ времени из одного компонента I и одного компонента II.

Первый этап производства довольно быстрый: гарантируется, что $$$1 \le t_1 \le 2$$$. За каждый этап производства отвечает отдельная фабрика, и каждая фабрика может работать только над соответствующим этапом (то есть, например, на фабрике, производящей компонент II, нельзя производить компонент I).

Все три процесса могут происходить параллельно, то есть пока, например, какой-то компонент I находится в производстве, другой уже произведенный ранее может обрабатываться в компонент II. Однако каждая из трех необходимых фабрик доступна в единственном числе, и в каждый момент времени может работать не более чем над одним компонентом или харвестером.

Чтобы быстро наладить добычу пряности, необходимо произвести $$$n$$$ харвестеров. За какое минимальное время это можно сделать?

Входные данные

В первой строке ввода дано единственное целое число $$$n$$$ — количество харвестеров, которые требуется произвести ($$$1 \le n \le 1000$$$).

Во второй строке через пробел даны три целых числа $$$t_1$$$, $$$t_2$$$ и $$$t_3$$$ — время, необходимое на каждом из этапов производства для получения единицы соответствующего продукта ($$$1 \le t_1 \le 2$$$; $$$1 \le t_2, t_3 \le 10^5$$$).

Выходные данные

Выведите единственное целое число — минимальное время, необходимое для производства $$$n$$$ харвестеров.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллыДоп. ограничения Необходимые подзадачи Информация о проверке
0примеры из условияполная
17$$$n = 1$$$полная
211$$$t_1 = t_2 = 1$$$, $$$t_3 \ge 2$$$полная
315$$$t_1 = 1$$$2первая ошибка
410$$$t_1 = t_2 \ge t_3$$$первая ошибка
510$$$t_1 = t_2$$$2, 4первая ошибка
615$$$n \le 6$$$, $$$t_2, t_3 \le 3$$$первая ошибка
719$$$n \le 100$$$, $$$t_2, t_3 \le 100$$$0, 6первая ошибка
813нет0 – 7первая ошибка

Примеры

Входные данные
1
1 5 6
Выходные данные
12
Входные данные
2
2 1 4
Выходные данные
12
Входные данные
10
1 7 20
Выходные данные
208

Примечание

В первом примере к условию:

  1. Можно произвести первый компонент типа I в момент времени $$$1$$$, после чего вторая фабрика может сразу начать из нее изготавливать компонент II.
  2. В момент времени $$$1 + 5 = 6$$$ он будет готов, и к этому времени первая фабрика произведет еще $$$5$$$ компонентов типа I.
  3. Один из них вместе с только что изготовленным компонентом типа II можно сразу же передать на третью фабрику, и в момент времени $$$6 + 6 = 12$$$ изготовить харвестер.