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>

#define PAUSE system("pause")
#define LLI long long int
#define LD long double
#define PB push_back
#define PF push_front
#define MP make_pair
#define FORi(i, a, b) for(int i = a; i < b ; ++i)
#define FORd(i, a, b) for(int i = a; i > b ; --i)

using namespace std;

int main() {
	int n,k;
	cin >> n >> k;
	vector<int> a(n);
	FORi(i,0,n){
		cin >> a[i];
	}
	
	int mask = 0;
	LLI ans = 1e16;
	const int INF = 1 << n;
	while(mask < INF){
		mask++;
		int cnt = 0;
		FORi(i,0,n){
			cnt += (mask>>i) & 1;
		}
		if (cnt != k){
			continue;
		}
		
		LLI cost = 0, h = 0;
		FORi(i,0,n){
			LLI added = 0;
			if ((mask>>i) & 1){
				if (h >= a[i]){
					added = h + 1 - a[i];
				}
			}
			h = max(h, a[i]+added);
			cost += added;
		}
		ans = min(ans, cost);
	}
	cout << ans;
	cout << endl;
	return 0;
}