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/env python
import os
import sys
from io import BytesIO, IOBase
from bisect import bisect_left,bisect_right
import threading 
from collections import Counter,defaultdict  
arr=[]




def main():
    for _ in range(1):
        n,k=map(int,input().split())
        arr=list(map(int,input().split()))
        g_c=0
        s_c=0
        done=0
        ans=float('inf')
        a=list(set(arr))
        a.sort()
        c=Counter(arr)
        c=defaultdict(int,c.items())

        for i in arr:
            if i>a[0]:
                g_c+=i-(a[0]+1)

        g_p=a[0]+1
        s_p=a[0]-1
        for i_,can in enumerate(a):
            
            k_=k-c[can]

            g_c=max(0, g_c-(can+1 - g_p)*(n-done-c[can]))
            if can>g_p:
                g_c=g_c-(can-g_p)*(c[can])
            s_c=s_c+(can-1 -s_p)*done

            # print(i_,can,done,g_c,s_c,ans)
            
            if k_<=0:
                ans=0
            elif s_c<g_c and done>=k_:
                ans=min(ans,s_c+k_)
            elif (n-done-c[can])>=k_:
                ans=min(ans,g_c+k_)
            else:
                ans=min(ans,g_c+s_c+k_)

            done+=c[can]
            s_c-=c[can]
            g_p=can+1
            s_p=can-1


            

        print(ans)

        




    
 
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# endregion
 
if __name__ == "__main__":
    main()