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 itertools
import copy
N, K = map(int, input().split())
A =list(map(int, input().split()))
ans=10**15
for c in itertools.product([0,1],repeat=N):
    a=copy.deepcopy(A)
    sm=0
    for i in range(1,N):
        if c[i]==1:
            if a[i]<=max(a[:i]):
                sm+=max(a[:i])-a[i]+1
                a[i]=max(a[:i])+1
    cnt=1
    for i in range(1,N):
        if max(a[:i])<a[i]:
            cnt+=1
    if cnt==K:
        ans=min(ans,sm)
print(ans)

