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:
// package algorithm.div629;

import java.io.*;
import java.util.StringTokenizer;

/**
 * Created with: IntelliJ IDEA
 * Function:
 * User: zhangzhe041@ke.com
 * Date: 2020-03-29 13:17:32
 */
public class MakekEqual {
    long[] a;
    MakekEqual() throws IOException {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = in.nextInt();
        int k = in.nextInt();
        a = new long[n + 1];
        for(int i = 1; i <= n; i++){
            a[i] = in.nextLong();
        }
        sort(a, 1, n);
        long[] pre = new long[n + 2];
        long[] suf = new long[n + 2];
        int[] cnt = new int[n + 2];
        for(int i = 1; i <=n ;i++){
            pre[i] = pre[i - 1] + a[i];
        }
        for(int i = n; i >= 1; i--) suf[i] = suf[i + 1] + a[i];
        for(int i = 1; i <= n; i++){
            if(a[i] == a[i - 1]) cnt[i] = cnt[i - 1] + 1;
            else cnt[i] = 1;
            if(cnt[i] >= k){
                out.print(0);
                out.close();
                return ;
            }
        }
        long ans = Long.MAX_VALUE;
        for(int i = 1; i <= n;i++){
            if(i >= k) ans = Math.min(ans, i*a[i] - pre[i] - (i - k));
            if(n - i + 1 >= k) ans = Math.min(ans, suf[i] - a[i] *(n - i + 1) - (n - i + 1 - k));
            ans = Math.min(i*a[i] - pre[i] + suf[i] - a[i]*(n - i + 1) - (n - k), ans);
        }
        out.print(ans);
        out.close();
    }

    public static void main(String[] args) throws IOException {
        new MakekEqual();
    }
//    public static int[] radixSort(int[] a)
//    {
//        int[] na = new int[a.length];
//        {
//            int[] b = new int[65537];
//            for(int i = 0;i < a.length;i++)b[1+(a[i]&0xffff)]++;
//            for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
//            for(int i = 0;i < a.length;i++)na[b[a[i]&0xffff]++] = a[i];
//            int[] c = a; a = na;na = c;
//        }
//        {
//            int[] b = new int[65537];
//            for(int i = 0;i < a.length;i++)b[1+(a[i]>>>16)]++;
//            for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
//            for(int i = 0;i < a.length;i++)na[b[a[i]>>>16]++] = a[i];
//            int[] c = a; a = na;na = c;
//        }
//        return a;
//    }
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }
        public boolean ready() throws IOException {
            return br.ready();
        }
    }
    public static void sort(long arr[], int start, int end) {
        if(start>=end)
            return;
        int mid=(start+end)/2;
        sort(arr,start,mid);
        sort(arr,mid+1,end);
        merge(arr,start,mid,end);
    }
    private static void merge(long arr[], int start, int mid, int end) {
        int i, j=mid+1,c=0;
        long temp[]= new long[end-start+1];
        for(i=start;i<=mid && j<=end;c++) {
            if(arr[i]<=arr[j]) {
                temp[c]=arr[i];
                i++;
            }
            else {
                temp[c]=arr[j];
                j++;
            }
        }
        while(i<=mid) {
            temp[c]=arr[i];
            i++;c++;
        }
        while(j<=end) {
            temp[c]=arr[j];
            j++;c++;
        }
        c=0;
        for(i=start;i<=end;i++,c++)
            arr[i]=temp[c];
    }
}