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 N, K, A[20], req[20];

int main() {
	scanf("%d%d", &N, &K);
	for (int i = 0; i < N; i++) scanf("%d", &A[i]);
	int cur = 0;
	for (int i = 0; i < N; i++) {
		req[i] = cur;
		cur = max(cur, A[i] + 1);
	}
	long long mini = 100000000000000000ll;
	for (int i = 0; i < (1 << N); i++) {
		if (__builtin_popcount(i) == K) {
			vector<int> v, idx;
			for (int j = 0; j < N; j++) {
				if (i & (1 << j)) {
					v.push_back(A[j]);
					idx.push_back(j);
				}
			}
			long long ans = 0;
			for (int j = 1; j < v.size(); j++) {
				if (v[j] < max(v[j - 1] + 1, req[idx[j]])) {
					ans += max(v[j - 1] + 1, req[idx[j]]) - v[j];
					v[j] = max(v[j - 1] + 1, req[idx[j]]);
				}
			}
			mini = min(mini, ans);
		}
	}
	printf("%lld\n", mini);
}
