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
def nasu(n):
  L = [0] * N
  for i in range(N):
    if n >> i & 1:
      L[i] = 1
  ans = 0
  t = a[0]
  for i in range(1, N):
    if L[i] == 1:
      if t >= a[i]:
        ans += t - a[i] + 1
        t = t + 1
      else:
        t = a[i]
    else:
      t = max(t, a[i])
  return ans

N, K = list(map(int, input().split()))
a = list(map(int, input().split()))

ans = 15 * 10 ** 9 

n = (1 << K) - 1
while n < (1 << N):
  ans = min(ans, nasu(n))

  x = n & -n
  y = n + x
  n = ((n & ~y) // x >> 1) | y

print(ans)