Саша — очень весёлый парень, поэтому он никогда не сидит на месте. В стране, где живёт Саша, есть \(n\) городов. Все они расположены на одной прямой и, для удобства, пронумерованы целыми числами от \(1\) до \(n\) в возрастающем порядке. Расстояние между любой парой соседних городов составляет \(1\) километр. Так как движение в стране одностороннее, то из города с номером \(x\) можно попасть в город с номером \(y\) только если \(x < y\).
Однажды Саша решил отправиться в путешествие по стране и посетить все \(n\) городов. Путешествовать он будет на своей машине Cheetah-2677. Вместимость бака у данной модели составляет \(v\) литров, а на \(1\) километр пути она тратит ровно \(1\) литр топлива. Изначально бак пуст. Саша находится в городе с номером \(1\) и хочет попасть в город с номером \(n\). В каждом городе есть заправка, причём в \(i\)-м городе \(1\) литр бензина стоит ровно \(i\) долларов. Очевидно, что в любой момент времени, в баке его машины может быть не более \(v\) литров топлива.
Саша не любит тратить деньги впустую, поэтому хочет узнать, какую минимальную сумму придётся взять с собой, чтобы доехать до последнего города, покупая топливо там, где он захочет. Помогите ему в этом!
Примечание
В первом примере Саша может заправить \(2\) литра за \(2\) доллара (\(1\) доллар за литр) в первом городе, доехать до второго города, потратив \(1\) литр, затем заправить \(1\) литр за \(2\) доллара во втором городе и доехать до города \(4\), не совершая дополнительных остановок. Поэтому ответ \(1+1+2=4\).
Во втором примере объём бака позволяет, заправив его полностью в первом городе, доехать до последнего города без остановок в других городах.