Задача C. Второе дыхание ≡

Условие

Тимофей всерьез занялся марафонским бегом. Он бережно относится к своему здоровью, тщательно подбирает рацион питания и тренируется, тренируется, тренируется...

Соревнования по марафону проходят на стадионе, всем участникам необходимо пробежать ровно n кругов. Тимофей после многомесячных тренировок точно узнал свои возможности: первый круг он пробежит за t минут, затем начнет сказываться усталость от уже преодолённой дистанции, поэтому второй круг он пробежит медленнее - за t + a минут, третий - за t + 2 ⋅ a, и т.д., то есть m-ый круг Тимофей пробежит за t + (m − 1) ⋅ a минут. Однако, как только время, затраченное на очередной круг станет строго больше v, у марафонца откроется второе дыхание и все остальные круги он будет бежать с постоянным временем v.

Определите, сколько минут потребуется Тимофею для того, чтобы пробежать n кругов?

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

В единственной строке через пробел записаны четыре неотрицательных целых числа: n, t, a и v.

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

Выведете одно натуральное число - время бега в минутах. Гарантируется, что ответ не превысит 10¹⁸.

Ограничения

1 ≤ n ≤ 10¹²

1 ≤ t ≤ 100

0 ≤ a ≤ 100

1 ≤ v ≤ 10¹⁸

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

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

Подзадача 1: 0 ≤ n ≤ 10⁵, баллы: 30.

Подзадача 2: нет дополнительных ограничений, баллы: 70.

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

В первом примере Тимофею нужно пробежать 8 кругов. Первый круг он пробежит за 10 минут. Второй - за 12, третий - за 14, четвертый - за 16. После четвертого круга время, затрачиваемое на круг, стало больше 15, поэтому пятый круг спортсмен пробежит за 15 минут, на шестой (и все оставшиеся) круги марафонец будет тратить те же 15 минут.

Итого в сумме получится 10 + 12 + 14 + 16 + 4 * 15 = 112.

Во втором примере Тимофей пробегает первый круг за 100 минут, второй - за 10.

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

8 10 2 15

112

2 100 0 10

110