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 <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;

int main() {
  int N, K;
  while (cin >> N >> K) {
    vector<ll> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    ll ans = 1ll << 62;
    for (int m = 0; m < (1 << N); m++) {
      if (__builtin_popcount(m) != K) continue;
      ll mx = 0;
      ll cost = 0;
      for (int i = 0; i < N; i++) {
        if ((m >> i) & 1) {
          ll t = max(mx + 1, a[i]);
          cost += t - a[i];
          mx = t;
        } else {
          mx = max(mx, a[i]);
        }
      }
      ans = min(ans, cost);
    }
    cout << ans << endl;
  }
  return 0;
}
