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;

int main() {
  int N,K; cin >> N >> K;
  long ans = 15000000000;
  vector<long> a(N);
  for (int i =0; i<N; i++) cin >> a[i]; 
  vector<long> maxA(N); maxA[0] = a[0];
  for (int i =1; i<N; i++)  
    maxA[i] = max(a[i-1],maxA[i-1]);
  
  for (int i =0; i< (1<<(N-1)); i++) {
    bitset<14> bit(i);
    long count =0;
    if (bit.count() == K-1) {
      long tmp = a[0]; int k =0; 
      for (int j =0; j<N-1; j++) {
        if (bit.test(j)) {
          k++;
          tmp = max(tmp,maxA[j+1]);
          if (a[j+1] - tmp <= 0) {
            count += tmp - a[j+1] + 1;
            tmp = tmp + 1;
          } else {
            tmp = a[j+1];
          }
          if (k == K) break;
        }
      }
      ans = min(count,ans);
    }
  }
  cout << ans << endl;  
}