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())
a = list(map(int,input().split()))
lis = [x for x in range(1,N)]
m = 10**15

for con in itertools.combinations(lis, K-1):
  mm = 0
  f = a[0]
  for i in range(K-1):
    if f+1 <= a[con[i]]:
      f = a[con[i]]
    else:
      mm += (f+1) - a[con[i]]
      f += 1
    for j in range(con[i]-1):
      if a[j] >= f:
        mm = 10**15
        break
    else:
      continue
    break
  m = min(m,mm)
  
print(m)