A. Гонщик Макс
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Макс — звезда уличных гонок. Сегодня перед ним длинный прямой проспект, и он хочет проехать по нему как можно дальше за отведённые $$$T$$$ секунд, пока улицы свободны.

Болид Макса описывается двумя числами: прочностью $$$P$$$ и максимальной безопасной скоростью $$$U$$$. Перед стартом болид стоит на месте, его скорость равна $$$0$$$.

Заезд идёт по секундам. В начале каждой секунды Макс делает ровно одно из трёх действий: сохраняет текущую скорость, увеличивает её на $$$1$$$ или уменьшает на $$$1$$$. Скорость не может стать отрицательной, поэтому при нулевой скорости уменьшить её нельзя. После этого в течение секунды болид проезжает столько метров, чему равна его текущая скорость (уже после изменения).

Обозначим текущую скорость через $$$S$$$. Если на этой секунде $$$S \gt U$$$, двигатель идёт вразнос: прочность падает, и значение $$$P$$$ уменьшается на $$$S - U$$$. Если в какой-то момент прочность становится отрицательной, то есть $$$P \lt 0$$$, болид выходит из строя, и заезд проигран. При $$$P = 0$$$ болид ещё держится.

Помогите Максу: какое максимальное суммарное расстояние он может проехать ровно за $$$T$$$ секунд, ни разу не выведя болид из строя?

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

В единственной строке заданы три целых числа $$$P$$$, $$$U$$$ и $$$T$$$ ($$$0 \le P \le 10^{18}$$$, $$$0 \le U \le 10^9$$$, $$$1 \le T \le 10^9$$$) — прочность болида, максимальная безопасная скорость и длительность заезда.

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

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

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

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

В данной задаче $$$10$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$10$$$ баллов. Решения, корректно работающие при $$$P, U, T \le 1000$$$, наберут не менее $$$50$$$ баллов.

Примеры
Входные данные
2 2 3
Выходные данные
6
Входные данные
3 2 6
Выходные данные
14
Примечание

В первом примере выгодно в начале каждой секунды увеличивать скорость на $$$1$$$. Тогда скорость превысит максимальную безопасную скорость на $$$1$$$ только в начале третьей секунды, от чего прочность уменьшится на $$$1$$$ и станет равной $$$1$$$, что допустимо. В таком случае болид проедет $$$1 + 2 + 3 = 6$$$.

Во втором примере один из вариантов оптимально менять скорость такой:

  • В начале первой секунды увеличить скорость на $$$1$$$, она становится равной $$$1$$$.
  • В начале второй секунды увеличить скорость на $$$1$$$, она становится равной $$$2$$$.
  • В начале третьей секунды увеличить скорость на $$$1$$$, она становится равной $$$3$$$, после этого прочность уменьшается на $$$3 - U = 1$$$ и становится равной $$$2$$$, что допустимо.
  • В начале четвертой секунды уменьшить скорость на $$$1$$$, она становится равной $$$2$$$, значит, прочность не уменьшается, так как $$$2 \leq U$$$.
  • В начале пятой секунды увеличить скорость на $$$1$$$, она становится равной $$$3$$$, прочность уменьшается на $$$1$$$ и становится равной $$$1$$$, что допустимо.
  • В начале шестой секунды оставить скорость прежней, она равна $$$3$$$, значит, прочность уменьшается на $$$1$$$ и становится равной $$$0$$$, что допустимо.

В таком сценарии болид проезжает $$$1 + 2 + 3 + 2 + 3 + 3 = 14$$$.