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 int64_t
signed main(){
  int n,k,a[100],sum,ans=-1,ma,q;
  cin>>n>>k;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  for(int i=0;i<(1<<(n));i++){
    sum=0;
    q=1;
    for(int j=0;j<n;j++){
      if(j==0) ma=a[0];
      if(i&(1<<j)&&j!=0){
	if(ma>=a[j]){
	  sum+=abs(a[j]-(ma+1));
	  ma+=1;
	  q++;
	}
	else{
	  q++;
	  ma=max(ma,a[j]);
	}
      }
      else{
	if(ma<a[j]){
	  q++;
	  ma=a[j];
	}
      }
    }
    //cout<<q<<"\n";
    if(ans==-1&&q>=k) ans=sum;
    if(q>=k) ans=min(ans,sum);
  }
  cout<<ans<<"\n";
}
