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>
#include<algorithm>
#define M 11451411451411451
using namespace std;
 
long long a[20],n,k;
 
long long F(long long q){
	bool t[20];
	long long r=2;
	for(int i=0;i<20;i++){
		if(q%r>=(r/2))t[i]=true;
		else t[i]=false;
		r*=2;
	}
	long long cnt=1,h=a[0],ret=0;
	for(int i=0;i<n-1;i++){
		if(t[i]){
			if(h+1>a[i+1]){
				ret+=h+1-a[i+1];
				h++;
			}
			else h=a[i+1];
			cnt++;
		}
		h=max(h,a[i+1]);
	}
	if(cnt>=k)return ret;
	return M;
}
 
int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++)cin>>a[i];
	long long ans=M;
	for(long long i=0;i<(1<<(n-1));i++){
		ans=min(ans,F(i));
	}
	cout<<ans<<endl;
	return 0;
}