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<vector>
#include<cstring>
#include<queue>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstdlib>
#include <clocale>
#include<cmath>
#include<sstream>
#include<set>
#include<stack>
using namespace std;
#define fr(i,n) for(int i=0;i<n;i++)
const int INF=0x3f3f3f3f;
const int MX=1e4+10;
typedef long long ll;
typedef pair<int ,int> p;
int main(){
	int n,k;
	ll num[22];
	cin>>n>>k;
	fr(i,n)cin>>num[i];
	ll ans=1e18;
	fr(i,1<<n){
		int s=0;
		fr(j,n)if((i>>j)&1)s++;
		if(s!=k)continue;
		ll ma=0,temp=0;
		fr(j,n){
			if((i>>j)&1)
			{
				if(num[j]<=ma){
					temp+=ma-num[j]+1;
				     ma++;
				}
				else ma=num[j];
			}
			else
				ma=max(ma,num[j]);
		}
		ans=min(ans,temp);
	}
	cout<<ans<<endl;
    //system("pause");
    return 0;
}