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 <cmath>

using namespace std;

#define ll long long 
#define REP(i, n) for(int i = 0; i < n; i++)

ll n,k,s[20], ans = (ll)1 << 60;
int main(){
	cin >> n >> k;
	REP(i, n) cin >> s[i];
	REP(i,1<<n){
		ll cnt = 0,now = 0,nans = 0;
		bool ok = true;
		REP(j, n) if(i & (1 << j)) cnt++;
		if(cnt >= k){
			REP(j, n){
				if(i & (1 << j)){
					nans += max(now + 1, s[j]) - s[j];
					now = max(now + 1, s[j]);
					REP(k, j) {
						if(s[k] > now) ok = false;
					}
				}
			}
			if(ok) ans = min(ans, nans);
		}
	}
	cout << ans << endl;
}