Макс — звезда уличных гонок. Сегодня перед ним длинный прямой проспект, и он хочет проехать по нему как можно дальше за отведённые $$$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$$$.
| Name |
|---|