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>
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define reps(i, m, n) for (int i = m; i < n; i++)
using namespace std;
typedef long long ll;

int main(){
  int n, k;
  scanf("%d %d", &n, &k);
  vector<ll> a(n);
  rep(i, n)scanf("%lld", &a[i]);
  
  ll ans = pow(10, 11);
  int count;
  ll sub, minimum;
  
  rep(i, pow(2, n)){
    count = 1;
    sub = 0;
    minimum = a[0];
    
    reps(j, 1, n){
      if (a[j] > minimum){
        minimum = a[j];
        count++;
        continue;
      }
      if ((i>>j)&1){
        count++;
        minimum++;
        sub += minimum-a[j];
      }
    }
    if ((count >= k) and (ans > sub)){
      ans = sub;
    }
  }
    
  
  printf("%lld\n", ans);
  
  return 0;
}