Problem: You are given the array a consisting of n elements and the integer k ≤ n.

You want to obtain at least k equal elements in the array a. In one move, you can make one of the following two operations:

  * Take one of the minimum elements of the array and increase its value by one (more formally, if the minimum value of a is mn then you choose such index i that a_i = mn and set a_i := a_i + 1); 
  * take one of the maximum elements of the array and decrease its value by one (more formally, if the maximum value of a is mx then you choose such index i that a_i = mx and set a_i := a_i - 1). 



Your task is to calculate the minimum number of moves required to obtain at least k equal elements in the array.

Input

The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 2 ⋅ 10^5) — the number of elements in a and the required number of equal elements.

The second line of the input contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9), where a_i is the i-th element of a.

Output

Print one integer — the minimum number of moves required to obtain at least k equal elements in the array.

Examples

Input


6 5
1 2 2 4 2 3


Output


3


Input


7 5
3 3 2 1 1 1 3


Output


4

Solution (in PYTHON3):

Solution:
#!/usr/bin/python3

import array
import bisect
import math
import os
import random
import re
import sys
from typing import List, Any

sys.setrecursionlimit(10000)

INIT = -1
INF = 10**18

n: int
k: int
a: List[int]
pre: List[int]

def printf(format: str, *args):
  sys.stdout.write(format % args)


def lo(l: int, r: int, x: int) -> int:
  """Determines cost to increase [l,r) to x."""
  if r <= l:
    return 0
  cnt = r - l
  got = pre[r - 1]
  want = x * cnt + l * (x - 1)
  return want - got


def hi(l: int, r: int, x: int) -> int:
  """Determines cost to reduce [l,r) to x."""
  if r <= l:
    return 0
  cnt = r - l
  got = pre[n - 1]
  if l > 0:
    got -= pre[l - 1]
  want = cnt * x + (n - r) * (x + 1)
  return got - want


def main():
  global n, k, a, pre
  [n, k] = list(map(int, input().strip().split(' ')))
  a = list(map(int, input().strip().split(' ')))

  a.sort()
  pre = array.array('q', [0]) * n
  
  for i in range(n):
    if i > 0:
      pre[i] = pre[i - 1]
    pre[i] += a[i]

  ans = INF
  for i in range(n):
    x = a[i]
    l = bisect.bisect_left(a, x, 0, i)  # left extent of x
    r = bisect.bisect_right(a, x, i, n) - 1  # right extent of x

    lgot = i - l
    rgot = r - i
    got = 1 + lgot + rgot
    if got >= k:
      ans = 0
      break

    # case 1: min before max
    lneed = k - got
    lcost = 0
    lcan = min(l, lneed)
    lneed -= lcan
    lcost = lo(l - lcan, l, x)
    if lneed > 0:
      lcost += hi(r, r + lneed + 1, x)
    ans = min(ans, lcost)
    
    # case 2: max before min
    rneed = k - got
    rcan = min(n - 1 - r, rneed)
    rneed -= rcan
    rcost = hi(r, r + rcan + 1, x)
    if rneed > 0:
      rcost += lo(l - rneed, l, x)
    ans = min(ans, rcost)
#    printf("i %d lcost %d rcost %d\n", i, lcost, rcost)

  print(ans)

  
if __name__ == '__main__':
  main()