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<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n,k;
  cin>>n>>k;
  int a[n];
  for(int i=0;i<n;i++) cin>>a[i];
  int comb=(1<<k)-1;
  int ans=1LL<<50LL;
  while(comb<(1<<n)){
    int tmp=0,res=0;
    for(int i=0;i<n;i++){
      if((comb>>i)&1){
	if(tmp<a[i]){
	  tmp=a[i];
	  continue;      
	}
	res+=(tmp+1)-a[i];
	tmp++;
      }else{
	tmp=max(tmp,a[i]);
      }
    }
    //cout<<res<<endl;
    ans=min(ans,res);
    int x=comb&-comb;
    int y=comb+x;
    comb=((comb&~y)/x>>1)|y;
  }
  cout<<ans<<endl;
  return 0;
}
