Vlad’s favourite part of Halloween is giving out candy to trick or treaters. He has prepared a jar of pieces of candy to give out to the kids that will be visiting his home.
However, Vlad has noticed that the kids have devised a clever plan to get more candy from him this Halloween. The children will walk up to his house in order and if a child doesn't get at least times more candy than the previous child, they will cry to their parents that Vlad is an evil vampire.
Vlad can't have the children ruining his reputation, however he also realizes that he won’t have enough candy to please the kids. Instead, he decides that he’ll "trick" some of the kids by taking their candy to refill his jar (every child has enough candy for him to refill his jar back to candies). This will cause the child to cry to their parents and hurt his reputation, but hey it’s called "trick or treat" for a reason. After tricking a child, Vlad can either treat the next child with one candy (restarting the process), or also trick the next child.
Given the damage Vlad expects every child to cause to his reputation if he tricks them, can you figure out the minimum amount of damage that Vlad can cause to his reputation?
The first line of input contains two integers \(N, M\ (1 \le N, M \le 100\ 000)\).
The next line contains integers, where each integer represents the damage the child would cause to Vlad’s reputation if he tricked them.
The minimum amount of damage that Vlad can cause to his reputation.
Sample Input 1
3 5 3 3 3
Sample Output 1
Sample Input 2
4 3 1 3 2 3
Sample Output 2