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
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()

ll n, k;
vector<ll> a(20);

ll solve (vector<ll> &d) {
    ll mx = 0, res = 0, p = 0;
    rep(i, k) {
        while (p < d[i]) {
            mx = max(mx, a[p]);
            p++;
        }
        res += max(mx+1-a[p], 0ll);
        mx = max(mx+1, a[p]);
        p++;
    }
    return res;
}

int main() {
    cin >> n >> k;
    rep(i, n) cin >> a[i];
    ll ans = 1e15;
    rep(i, 1<<n) {
        vector<ll> d;
        rep(j, n) if (i>>j & 1) d.push_back(j);
        sort(all(d));
        if (d.size() != k) continue;
        ans = min(ans, solve(d));
    }
    cout << ans << endl;
    return 0;
}