Саша — очень весёлый парень, поэтому он никогда не сидит на месте. В стране, где живёт Саша, есть $$$n$$$ городов. Все они расположены на одной прямой и, для удобства, пронумерованы целыми числами от $$$1$$$ до $$$n$$$ в возрастающем порядке. Расстояние между любой парой соседних городов составляет $$$1$$$ километр. Так как движение в стране одностороннее, то из города с номером $$$x$$$ можно попасть в город с номером $$$y$$$ только если $$$x < y$$$.

Однажды Саша решил отправиться в путешествие по стране и посетить все $$$n$$$ городов. Путешествовать он будет на своей машине Cheetah-2677. Вместимость бака у данной модели составляет $$$v$$$ литров, а на $$$1$$$ километр пути она тратит ровно $$$1$$$ литр топлива. Изначально бак пуст. Саша находится в городе с номером $$$1$$$ и хочет попасть в город с номером $$$n$$$. В каждом городе есть заправка, причём в $$$i$$$-м городе $$$1$$$ литр бензина стоит ровно $$$i$$$ долларов. Очевидно, что в любой момент времени, в баке его машины может быть не более $$$v$$$ литров топлива.

Саша не любит тратить деньги впустую, поэтому хочет узнать, какую минимальную сумму придётся взять с собой, чтобы доехать до последнего города, покупая топливо там, где он захочет. Помогите ему в этом!