Перспективный пилот Максим участвует в гонке Формулы-100500 из $$$n$$$ кругов. Известно, что свежесть шин играет большую роль в скорости болида, поэтому все комплекты шин имеют параметр изношенности. Если Максим стартует круг на шинах изношенности $$$x$$$, то он проезжает этот круг за $$$x$$$ секунд, а изношенность этого комплекта шин в конце круга становится $$$x + 1$$$.

Всего у команды Максима есть два комплекта шин, первый комплект имеет изношенность $$$a$$$ и уже установлен на болид перед началом гонки. Запасной комплект имеет изношенность $$$b$$$. Перед каждым кругом Максим может сделать пит-стоп и сменить комплект шин на своей машине за $$$p$$$ секунд. Можно делать сколько угодно пит-стопов, в том числе можно сделать пит-стоп перед первым кругом и начать гонку на запасном комплекте, но время этого пит-стопа также будет добавлено к времени гонки.

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

В тестах общей стоимостью не менее 10 баллов дополнительно выполняется $$$n, a, b, p \leq 100$$$.

В тестах общей стоимостью не менее 20 баллов дополнительно гарантируется, что оптимально проехать все круги на одном комплекте шин.

В тестах общей стоимостью не менее 25 баллов дополнительно выполняется $$$n, a, b, p \leq 10\,000$$$.

В тестах общей стоимостью не менее 45 баллов дополнительно выполняется $$$n, a, b, p \leq 1\,000\,000$$$.