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<cstdio>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<functional>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<string.h>
#include<limits.h>
#define int long long
using namespace std;

int ans = LLONG_MAX;
int a, b;
int K[15];
int cost;
void saiki(int c, int d,int e) {//c個目まで見てd個とった 最高の高さはe
	if (c == a) {
		if (d >= b) {
			ans = min(ans, cost);
		}
		return;
	}
	if (K[c] > e) {
		saiki(c + 1, d + 1, K[c]);
	}
	else {
		saiki(c + 1, d, e);
		cost += e - K[c] + 1;
		saiki(c + 1, d + 1, e + 1);
		cost -= e - K[c] + 1;
	}
}
signed main() {
	 scanf("%lld%lld", &a, &b);
	 for (int c = 0; c < a; c++) {
		 scanf("%lld",&K[c]);
	 }
	 saiki(1, 1, K[0]);
	 printf("%lld\n", ans);
}