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;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define rrep(i,n) for (int i = 1; i <= (n); i++)
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int,int>;
using Pl = pair<ll,ll>;

ll N, K, ans;

int main()
{
	cin >> N >> K;
	vector<ll>a(N), v(N + 1);
	rep(i, N)
	{
		cin >> a[i];
		v[i + 1] = a[i];
	}
	rep(i, N) v[i + 1] = max(v[i + 1], v[i]);
	ans = 112345678901;
	rep(bit, (1ll << N))
	{
		vector<ll>idxs;
		rep(i, N)
		{
			if (bit&(1ll << i)) idxs.push_back(i);
		}
		if (idxs.size() != K) continue;
		ll maxH = 0, res = 0;
		rep(i, K)
		{
			maxH = max(maxH, v[idxs[i]]);
			if (a[idxs[i]] <= maxH)
			{
				++maxH;
				res += maxH - a[idxs[i]];
			}
			else maxH = a[idxs[i]];
		}
		ans = min(ans, res);
	}
	cout << ans << endl;
	return 0;
}
