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
import copy

n,m = map(int, input().split())
li = list(map(int, input().split()))

ans = 10**18
for i in range(2**n):
    check = [0]*n
    
    for j in range(n):
        if ((i >> j) & 1):
            check[n - j - 1] = 1

    if sum(check) < m:
        continue
    
    li_copy = copy.copy(li)
    tmp_ans = 0
    
    for x in range(n):
        if x == 0:
            continue
        if check[x] == 0:
            continue
        
        s = max(li_copy[0:x])
        t = li_copy[x]

        if s >= t:
            tmp_ans += s - t + 1
            li_copy[x] = s + 1
    ans = min(ans, tmp_ans)
    
print(ans)