Пряность или меланж — один из самых ценных ресурсов во вселенной. Когда Дом Атрейдесов прибыл на планету Арракис, им было поручено в том числе наладить добычу пряности после того, как планету покинул Дом Харконненнов.
На первых этапах Атрейдесам был доступен только один харвестер (комбайн) для сбора, поэтому необходимо было срочно наладить их производство.
Первый этап производства довольно быстрый: гарантируется, что $$$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 | – | примеры из условия | полная | |
1 | 7 | $$$n = 1$$$ | полная | |
2 | 11 | $$$t_1 = t_2 = 1$$$, $$$t_3 \ge 2$$$ | полная | |
3 | 15 | $$$t_1 = 1$$$ | 2 | первая ошибка |
4 | 10 | $$$t_1 = t_2 \ge t_3$$$ | первая ошибка | |
5 | 10 | $$$t_1 = t_2$$$ | 2, 4 | первая ошибка |
6 | 15 | $$$n \le 6$$$, $$$t_2, t_3 \le 3$$$ | первая ошибка | |
7 | 19 | $$$n \le 100$$$, $$$t_2, t_3 \le 100$$$ | 0, 6 | первая ошибка |
8 | 13 | нет | 0 – 7 | первая ошибка |
1 1 5 6
12
2 2 1 4
12
10 1 7 20
208
В первом примере к условию: