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 = sys.stdin.readline

from collections import Counter

n,k=map(int,input().split())
A=list(map(int,input().split()))

S=sorted(set(A))+[1<<60]
C=Counter(A)

if max(C.values())>=k:
    print(0)
    sys.exit()

L=[0]
LK=[0]
ko=0
for i in range(len(S)-1):
    ko+=C[S[i]]
    LK.append(ko)
    L.append(L[-1]+ko*(S[i+1]-S[i]))

R=[0]*len(S)
RK=[0]*len(S)
ko=0
for i in range(len(S)-1,-1,-1):
    ko+=C[S[i]]
    RK[i-1]=ko
    R[i-1]=(R[i]+ko*(S[i]-S[i-1]))
R[-1]=0
ANS=1<<61
for i in range(len(S)-1):
    rest=k-C[S[i]]

    if i>=1:
        if rest<=LK[i]:
            ANS=min(ANS,L[i-1]+(S[i]-S[i-1])*rest)
        else:
            ANS=min(ANS,L[i]+R[i+1]+(S[i+1]-S[i])*RK[i]-(RK[i]-rest+LK[i]))

    if i<len(S)-1:
        if rest<=RK[i]:
            ANS=min(ANS,R[i+1]+(S[i+1]-S[i])*rest)
        else:
            ANS=min(ANS,R[i]+L[i-1]+(S[i]-S[i-1])*LK[i]-(LK[i]-rest+RK[i]))

print(ANS)