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<bits/stdc++.h>
using namespace std;


int main()
{
	int n, k;
	cin>> n >> k;
	vector<int> a(n-1);
	
	int a0;
	cin>> a0;
	for(int i=0;i<n-1;i++){
		cin>>a[i];
	}
	
	long long ans = 1E13;
	for(int bit=0;bit<(1<<(n-1));bit++){
		int col = 1;
		vector<bool> look(n-1);
		long long cost = 0;
		for(int i=0;i<n-1;i++){
			if(bit&(1<<i)){
				look[i] = 1;
				col++;
			}
		}
		if(col<k) continue;
		
		int hight = a0;
		for(int i=0;i<n-1;i++){
			if(look[i]){
				if(a[i]<hight+1){
					cost += (hight+1-a[i]);
					hight++;
				}else{
					hight = a[i];
				}
			}else{
				if(hight<a[i]){
					hight = a[i];
				}
			}
		}
		if(cost<ans) ans = cost;
	}
	cout<<ans<<endl;
}
