Пандемия охватила все страны мира, и Берляндия не стала исключением. Даже на Всеберляндской олимпиаде по информатике были введены противовирусные меры.
Всего в олимпиаде участвуют $$$n$$$ человек, и, чтобы соблюсти все предписания руководства, жюри олимпиады решило приглашать участников на тур по одному с интервалом $$$x$$$ минут. Таким образом первый участник начнёт тур в момент времени $$$0$$$, второй участник начнёт тур в момент времени $$$x$$$, третий — в момент времени $$$2 \cdot x$$$ и так далее.
Несмотря на разное время начала, длительность тура для каждого участника составляет ровно $$$t$$$ минут. Из-за этого некоторые участники заканчивают писать тур раньше остальных. Когда участник заканчивает писать тур, величина недовольства организацией олимпиады для этого участника равна числу других участников, которые в текущий момент времени еще пишут или только начинают писать тур, но еще не закончили его.
Помогите организаторам олимпиады выяснить, чему равно суммарное недовольство всех участников олимпиады.
В первой строке вводится единственное целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^9$$$) — число участников олимпиады.
Во второй строке вводится единственное целое число $$$x$$$ ($$$1 \le x \le 2 \cdot 10^9$$$) — интервал в минутах между временами начала тура для участников.
В третей строке вводится единственное целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^9$$$) — длительность тура.
В единственной строке выведите одно число — суммарное недовольство всех участников олимпиады.
4 2 5
5
3 1 2
3
3 3 10
3
В первом примере первый участник начнёт писать тур в момент времени $$$0$$$ и закончит в момент времени $$$5$$$. К этому времени второй и третий участники уже начнут писать тур, поэтому недовольство первого участника будет равно $$$2$$$.
Второй участник начнёт писать в момент времени $$$2$$$ и закончит в момент времени $$$7$$$. К этому моменту третий и четвёртый участники уже начнут писать тур, поэтому недовольство второго будет равно $$$2$$$.
Третий участник начнёт писать тур в момент времени $$$4$$$ и закончит в момент времени $$$9$$$. К этому времени четвёртый участник уже начнёт писать тур, поэтому недовольство третьего будет равно $$$1$$$.
Четвёртый участник начнёт писать тур в момент времени $$$6$$$ и закончит в момент времени $$$11$$$. В момент времени $$$9$$$ уже никто не будет писать тур, поэтому недовольство четвёртого будет равно $$$0$$$.
Таким образом, суммарное недовольство всех участников будет равно $$$2+2+1+0=5$$$.
Во втором примере первый участник начнёт писать тур в момент времени $$$0$$$ и закончит в момент времени $$$2$$$. К этому моменту второй участник уже будет писать тур, а третий участник как раз начнёт в момент времени $$$2$$$. Поэтому недовольство первого участника будет равно $$$2$$$.
Второй участник начнёт в момент времени $$$1$$$ и закончит в момент времени $$$3$$$. К этому моменту только третий участник будет всё ещё писать тур.
Таким образом, суммарное недовольство всех участников будет равно $$$2+1=3$$$.
В данной задаче $$$20$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$5$$$ баллов. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при $$$n, x, t \le 10$$$, наберут не менее $$$25$$$ баллов.
Решения, корректно работающие при $$$n \le 1000$$$, наберут не менее $$$50$$$ баллов.
Решения, корректно работающие при $$$n \le 100\,000$$$, наберут не менее $$$75$$$ баллов.
