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
from itertools import combinations
INF = int(1e18)
def main():
    n, k = map(int, input().split())
    a = [int(i) for i in input().split()]
    p = [i for i in range(1,n)]
    #必ず見えるようにする建物の組合せを決める
    #左端の建物は常に見えるので注意する
    ans = INF
    for i in combinations(p, k-1):
        s = set(i)
        cost = 0
        mx = a[0]
        for j in range(1, n):
            if j in s:
                if a[j] > mx:
                    mx = a[j]
                    continue
                mx += 1
                cost += mx-a[j]
            mx = max(mx, a[j])
        ans = min(cost, ans)                
    print(ans)
main()