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.io.*;
import java.util.StringTokenizer;

/**
 * Created with: IntelliJ IDEA
 * Function:
 * User: zhangzhe041@ke.com
 * Date: 2020-03-29 18:50:47
 */
public class MakekEqualPlus {

    MakekEqualPlus() throws IOException {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = in.nextInt();
        int k = in.nextInt();
        long[] a = new long[n + 1];
        for(int i = 1; i <= n; i++){
            a[i] = in.nextLong();
        }
        long[] pre = new long[n + 2];
        long[] suf = new long[n + 2];
        sort(a, 1, n);
        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];
        }
        int[] cnt = new int[n + 1];
        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] - (n - i + 1)*a[i] - (n - i + 1 - k));
            ans = Math.min(ans, i * a[i] - pre[i] + suf[i] - (n - i + 1)*a[i] - (n - k));
        }
        out.print(ans);
        out.close();

    }

    private void sort(long[] arr, int start, int end){
        if(start >= end) return;
        int mid = start + (end - start) / 2;
        sort(arr, start, mid);
        sort(arr, mid +1, end);
        merge(arr, start, mid, end);
    }

    private void merge(long[] arr, int start, int mid, int end){
        int i = start, j = mid + 1;
        long[] help = new long[end - start + 1];
        int c = 0;
        while(i <= mid && j <= end){
            help[c++] = arr[j] < arr[i] ? arr[j++] : arr[i++];
        }
        while(i <= mid){
            help[c++] = arr[i++];
        }
        while(j <= end){
            help[c++] = arr[j++];
        }
        for(int k = 0; k < help.length; k++){
            arr[start + k] = help[k];
        }
    }

    public static void main(String[] args) throws IOException {
        new MakekEqualPlus();
    }


    private static class Scanner{
        StringTokenizer st;
        BufferedReader br;

        Scanner(InputStream inputStream) {
            br = new BufferedReader(new InputStreamReader(inputStream));
        }
        String next() throws IOException {
            while(st == null || !st.hasMoreTokens()){
                st = new StringTokenizer(br.readLine());
            }
            return st.nextToken();
        }
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
        long nextLong() throws IOException {
            return Long.parseLong(next());
        }
        String nextLine() throws IOException {
            return br.readLine();
        }

    }
}