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

N, K = map(int, input().split()) # Nは建物の数、K色以上に塗る
A = list(map(int, input().split()))
N_index = list(range(1,N)) # 一番左は固定なので

min_cost = float('inf')
for target_indexes in itertools.combinations(N_index, K-1): # N_indexからK-1個選ぶ方法を全通り試す
    cost = 0
    copy_A = A.copy()
    for i in target_indexes:
        if copy_A[i] <= max(copy_A[:i]):
            diff = max(copy_A[:i]) - copy_A[i] # ターゲットの建物の場合はそれより左側の建物のmaxより1だけ大きくする
            copy_A[i] += diff + 1
            cost += diff + 1

    min_cost = min(min_cost, cost)

print(min_cost)
