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 JAVA):

Solution:
import java.util.*;
import java.io.*;
import static java.lang.Math.*;
import static java.lang.System.*;
public class F
{
    public static void main(String[]args){
        InputReader sc= new InputReader(System.in);
        PrintWriter pw =new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        int len=sc.nextInt();
        int k=sc.nextInt();
        long min=999999999999999L;
        int[]arr=sc.nextIntArray(len);
        radixsort(arr,len);
        for(int i=k-1;i<arr.length;i++){
            if(arr[i]==arr[i-k+1]){
                System.out.println(0);
                return;
            }
        }
        
        int minloca=arr[(int)k-1];
        long smallsum=0;
        for(int i=0;i<k;i++){
        	smallsum+=minloca-arr[i];
        }
        long smallbig=0;
        for(int i=0;i<arr.length;i++){
        	if(arr[i]==minloca)smallbig=i;
        }
        min=Math.min(smallsum-(smallbig-k+1),min);

        int maxloca=arr[len-k];
        long bigsum=0;
        for (int i=len-1; i>len-1-k; i--) {
        	bigsum+=arr[i]-arr[len-k];
        }
        int bigsmall=0;
        for (int i=len-1; i>-1; i--) {
        	if(arr[i]==maxloca)bigsmall=i;
        }
        bigsum-=(len-k)-bigsmall;
        min=Math.min(min,bigsum);

        int amt=arr.length;
        int extra=amt-k;
        long sum=0;
        for(int i=0;i<arr.length;i++){
        	sum+=arr[i]-arr[0];
        }
        min=Math.min(min,sum-extra);
        for(long i=1;i<arr.length;i++){
        	sum-=((long)((long)arr.length-i))*((long)(arr[(int)i]-arr[(int)i-1]));
        	sum+=(i-0L)*((long)(arr[(int)i]-arr[(int)i-1]));
        	min=Math.min(min,sum-extra);
        }
        System.out.println(Math.max(0L,min));
        pw.flush();
    }
        static int getMax(int arr[], int n) 
    { 
        int mx = arr[0]; 
        for (int i = 1; i < n; i++) 
            if (arr[i] > mx) 
                mx = arr[i]; 
        return mx; 
    } 
  
    // A function to do counting sort of arr[] according to 
    // the digit represented by exp. 
    static void countSort(int arr[], int n, int exp) 
    { 
        int output[] = new int[n]; // output array 
        int i; 
        int count[] = new int[10]; 
        Arrays.fill(count,0); 
  
        // Store count of occurrences in count[] 
        for (i = 0; i < n; i++) 
            count[ (arr[i]/exp)%10 ]++; 
  
        // Change count[i] so that count[i] now contains 
        // actual position of this digit in output[] 
        for (i = 1; i < 10; i++) 
            count[i] += count[i - 1]; 
  
        // Build the output array 
        for (i = n - 1; i >= 0; i--) 
        { 
            output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 
            count[ (arr[i]/exp)%10 ]--; 
        } 
  
        // Copy the output array to arr[], so that arr[] now 
        // contains sorted numbers according to current digit 
        for (i = 0; i < n; i++) 
            arr[i] = output[i]; 
    } 
  
    // The main function to that sorts arr[] of size n using 
    // Radix Sort 
    static void radixsort(int arr[], int n) 
    { 
        // Find the maximum number to know number of digits 
        int m = getMax(arr, n); 
  
        // Do counting sort for every digit. Note that instead 
        // of passing digit number, exp is passed. exp is 10^i 
        // where i is current digit number 
        for (int exp = 1; m/exp > 0; exp *= 10) 
            countSort(arr, n, exp); 
    } 
    static class InputReader
    {
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;
        public InputReader(InputStream stream)
        {
                this.stream = stream;
        }
        public int snext()
        {
                if (snumChars == -1)
                        throw new InputMismatchException();
                if (curChar >= snumChars)
                {
                        curChar = 0;
                        try
                        {
                                snumChars = stream.read(buf);
                        } catch (IOException e)
                        {
                                throw new InputMismatchException();
                        }
                        if (snumChars <= 0)
                                return -1;
                }
                return buf[curChar++];
        }
        public int nextInt()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                int res = 0;
                do
                {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }
        public long nextLong()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                long res = 0;
                do
                {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }
        public double nextDouble()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                double res = 0;
                while(c<='9'&&c>='0'){
                    res*=10;
                    res+=c-'0';
                    c=snext();
                }
                if(c=='.'){
                    double decimal=0;
                    long multiplier=1;
                    c=snext();
                    do
                    {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        decimal *= 10;
                        decimal += c - '0';
                        multiplier*=10;
                        c = snext();
                    } while (!isSpaceChar(c));
                    return sgn*(res+decimal/multiplier);
                }else{
                    if(!isSpaceChar(c)){
                        throw new InputMismatchException();
                    }
                    return sgn*res;
                }
        }
        public int[] nextIntArray(int n)
        {
                int a[] = new int[n];
                for (int i = 0; i < n; i++)
                {
                        a[i] = nextInt();
                }
                return a;
        }
        public long[] nextLongArray(int n)
        {
                long a[] = new long[n];
                for (int i = 0; i < n; i++)
                {
                        a[i] = nextLong();
                }
                return a;
        }
        public String next(){return readString();}
        public String readString()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isSpaceChar(c));
                return res.toString();
        }
        public String nextLine()
        {
                int c = snext();
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isEndOfLine(c));
                if(isEndOfLine(res.charAt(res.length()-1)))
                return res.deleteCharAt(res.length()).toString();
                return res.toString();
        }
        public ArrayList<String> readAll(){
            ArrayList<String>a=new ArrayList<String>();
            try{
                while(true){
                    a.add(nextLine());
                }
            }catch(Exception e){
                
            }
            return a;
        }
        public boolean hasNext(){
            boolean hasnext=true;
            try{
                hasnext= stream.available()!=0;
            }catch(IOException e){
            }
            return hasnext||curChar<snumChars;
        }
        public boolean isSpaceChar(int c)
        {
                if (filter != null)
                        return filter.isSpaceChar(c);
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        private boolean isEndOfLine(int c)
        {
                return c == '\n' || c == '\r' || c == -1;
        }
        public interface SpaceCharFilter
        {
                public boolean isSpaceChar(int ch);
        }
    }
}