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 ll = int_fast64_t;

int main(){
        int n, k;
        scanf("%d %d", &n, &k);
        ll a[n];
        for(int i=0; i<n; i++) scanf("%ld", &a[i]);

        ll ans = 1e18;
        for(int i=0; i<(1<<n); i++){
                if(__builtin_popcount(i)<k) continue;

                ll cnt = 0, wall = 0;
                for(int j=0; j<n; j++){
                        if((i>>j)&1){
                                if(wall>=a[j]){
                                        cnt += wall-a[j]+1;
                                        wall++;
                                }
                        }
                        wall = std::max(wall, a[j]);
                }

                ans = std::min(ans, cnt);
        }

        printf("%ld\n", ans);
        return 0;
}