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;

using ll = long long;
#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

//int#define INF 1e9
const ll INF = 1LL << 61;

int main(){
  int N, K;
  cin >> N >> K;
  vector<ll> a(N);
  REP(i, N){
    cin >> a[i];
  }
  ll ans = INF;
  REP(b, 1<<N){
    ll pre = 0;
    ll cost = 0;
    int cnt = 0;
    REP(i, N){
      if(b>>i & 1){
        ll diff = max(0LL, pre-a[i]+1);
        assert(diff >= 0);
        cost += diff;
        pre = a[i] + diff;
        cnt++;
      }
      else{
        pre = max(pre, a[i]);
      }
    }
    if(cnt >= K){
      ans = min(ans, cost);
    }
  }
  cout << ans << endl;
  return 0;
}