Input Format


N K
a_1 a_2 a_3 ... a_N


Output Format

Print the minimum cost in one line. In the end put a line break.


Constraints

* 1 ≤ K ≤ N ≤ 15
* 1 ≤ a_i ≤ 10^9



Scoring

Subtask 1 [120 points]


* N = K

Subtask 2 [90 points]


* N ≤ 5
* a_i ≤ 7

Subtask 3 [140 points]


* There are no additional constraints.

Output Format

Print the minimum cost in one line. In the end put a line break.


Constraints

* 1 ≤ K ≤ N ≤ 15
* 1 ≤ a_i ≤ 10^9



Scoring

Subtask 1 [120 points]


* N = K

Subtask 2 [90 points]


* N ≤ 5
* a_i ≤ 7

Subtask 3 [140 points]


* There are no additional constraints.

Input Format


N K
a_1 a_2 a_3 ... a_N

Example

Input

5 5
3949 3774 3598 3469 3424


Output

1541
#include <iostream>
using namespace std;

typedef long long ll;


int main() {
ll n,k,a[15],m=1e18;
cin>>n>>k;
for(int i=0;i<n;i++){
    cin>>a[i];
}
for(int i=0;i<(1<<(n-1));i++){
    ll r=a[0],c=1,d=0;
    for(int j=0;j<n-1;j++){
        if(((i>>j)&1)==1){
            d+=max((ll)0,r-a[j+1]+1);
            r=max(r+1, a[j+1]);
            c++;
        }else if(a[j+1]>r){
          j=n;
          c=0;
        }
    }
    if(c>=k){
        m=min(m,d);
    }
}
cout<<m<<endl;
	return 0;
}