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
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long

using namespace std;

const ll INF = 100100100100;

int main() {
	int N, K;
	cin >> N >> K;

	vector <ll> a(N);
	for (int ii = 0; ii < N; ++ii){
		cin >> a[ii];
	}

	ll ans = INF;
	for (int n = 0; n < (1<<N); ++n){
		bitset< 1<<15 > bs(n);
		if (bs.count()!=K) continue;

		ll sum = 0;
		ll h = a[0];
		for (int ii = 1; ii < N; ++ii){
			if (bs[ii]){
				ll need;
				if (h < a[ii]){
					h = a[ii];
					need = 0;
				} else {
					h += 1;
					need = h - a[ii];
				}
				sum += need;
			} else {
				h = max(h, a[ii]);
			}
		}
		ans = min(ans, sum);
	}

	cout << ans << "\n";

	return 0;
}
