Lemony Snicket's Dangerous Duel

Jaewon City has a building with height $N$. There are $K$ pillars located in outer wall of the building, each numbered with $1, 2, \dots K$. One day, a fire broke out in the building. In order to extinguish it, VFD (Volunteer Fire Department) responded.

VFD consists of $K$ members. Each member will climb pillars from height $0$. In order to extinguish fire completely, every member should climb up to height $N$. Note that every member climbs distinct pillar.

Climbing the building without safety device is dangerous. So after one member climbs the building by $1$, his new location and other $K-1$ member's current location should be tied with rope for safety.

More formally, let $x$-th member be the member that climbs the $x$-th pillar. When he tries to climb from $H_x$ to $H_x + 1$, for each , -th member's current height , and -th member's new height should be tied with rope. The cost of tying the rope is . In conclusion, ropes are required for one step of climb, and the cost of climb is the sum of the cost of tying the ropes.

Calculate the minimum cost of climb for every member to reach height $N$.

The input is given in the following format:

$N \ K$ $A_{1,0} \ A_{1,1} \ \cdots \ A_{1,N}$

Print one integer: The minimal cost of every member to reach height $N$. It is guaranteed that the answer is no greater than $10^{18}$.

• $1 \leq N \leq 100 \ 000$.
• $2 \leq K \leq 200 \ 000$.
• $N\times K\le 200$.