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 
#define Rep(i, N) for(int i = 0; i < N; i++)
#define Reps(i, x, N) for(int i = x; i < N; i++)

#define pb push_back

const int LLINF = 1LL << 60;

signed main()
{
  int N, K;
  int A[25];
  int minv = LLINF;

  cin >> N >> K;
  Rep(i, N) cin >> A[i];
  
  Rep(i, 1 << N) {
    int cnt = 0, sum = 0, maxv = 0;

    Rep(j, N) {
      if((1 << j) & i) cnt++;
    }
    if(cnt != K) continue;

    Rep(j, N) {
      if((1 << j) & i) {
	sum += max(0LL, maxv + 1 - A[j]);
	maxv = max(maxv + 1, A[j]);
      } else {
	maxv = max(maxv, A[j]);
      }
    }

    minv = min(sum, minv);
  }

  cout << minv << endl;
      
  
  return 0;
}
