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 <string>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;
static const ll INF = 1000000000000000000ll;

int main(){
	ios_base::sync_with_stdio(false);
	int n, k;
	cin >> n >> k;
	vector<ll> a(n);
	for(int i = 0; i < n; ++i){ cin >> a[i]; }
	ll answer = INF;
	for(int i = 0; i < (1 << n); ++i){
		if(__builtin_popcount(i) != k){ continue; }
		ll last = 0, sum = 0;
		for(int j = 0; j < n; ++j){
			if(i & (1 << j)){
				const ll t = max(last + 1, a[j]);
				sum += t - a[j];
				last = t;
			}else{
				last = max(last, a[j]);
			}
		}
		answer = min(answer, sum);
	}
	cout << answer << endl;
	return 0;
}

