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:
import sys
input=lambda: sys.stdin.readline().rstrip()
import collections
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
C=collections.Counter(A)
AA=sorted(C.keys())
nn=len(AA)
L=[0]
H=[0,C[AA[0]]]
haba=0
for i in range(nn-1):
  haba+=C[AA[i]]
  L.append(L[-1]+haba*(AA[i+1]-AA[i]))
  H.append(H[-1]+C[AA[i+1]])
R=[0]
haba=0
for i in range(1,nn)[::-1]:
  haba+=C[AA[i]]
  R.append(R[-1]+haba*(AA[i]-AA[i-1]))
R=R[::-1]
if C[AA[0]]>=k:
  ans1=0
else:
  ans1=R[0]-(n-k)
if C[AA[-1]]>=k:
  ans2=0
else:
  ans2=L[-1]-(n-k)
ans=min((ans1,ans2))

for i in range(1,nn-1):
  a=AA[i]
  cur=float("inf")
  if C[a]>=k:
    cur=0
  else:
    res=k-C[a]
    if H[i]>=res:
      cur1=L[i]-(H[i]-res)
    else:
      cur1=L[i]+R[i]-(n-H[i+1]-(res-H[i]))
    if n-H[i]>=k:
      cur2=R[i]-(n-H[i+1]-res)
    else:
      cur2=R[i]+L[i]-(H[i]-(k-n+H[i]))
    cur=min(cur1,cur2)
  ans=min(ans,cur)
print(ans)