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 
const int inf = 1LL << 60;
signed main(void){
  int n,k; cin >> n >> k;
  vector<int>a(n);
  for(int i = 0; i < n; i++){ cin >> a[i];}
  int ans = inf;
  for(int bit = 0; bit < (1<<n); bit++){
    vector<bool> vec(n,false); int cnt = 0;
    for(int i = 0; i < n; i++){ 
      if( bit >> i & 1 ){ vec[i] = true; cnt++;}
    }
    if( cnt < k ){ continue;}
    int M = 0; int sum = 0;
    for(int i = 0; i < n; i++){
      if( vec[i] ){
        if( M >= a[i] ){ sum += M-a[i]+1;}
      }
      if( vec[i] ){ M = max(M+1,a[i]);}
      else{ M = max(M,a[i]);}
    }
    ans = min(ans,sum);
  }
  cout << ans << endl;
  return 0;
}
      