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>
#include <vector>
#include <string>
#define int long long
using namespace std;
int n, k, a[20], inf;
bool b[20];
int f(int i, int cnt) {
	if (i == n) {
		if (cnt != k)return inf;
		int m = 0, r = 0;
		for (int i = 0; i < n; i++) {
			if (b[i]) {
				if (m >= a[i]) {
					r += m++ + 1 - a[i];
				}
			}
			m = max(m, a[i]);
		}
		return r;
	}
	int r = f(i + 1, cnt);
	b[i] = 1;
	int r1;
	if (cnt == k - 1)r1 = f(n, cnt + 1);
	else r1 = f(i + 1, cnt + 1);
	b[i] = 0;
	return min(r, r1);
}
signed main() {
	cin >> n >> k;
	inf = 1000000000 * n + 10;
	for (int i = 0; i < n; i++)cin >> a[i];
	cout << f(0, 0) << endl;\
}