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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class C1328F {
    public static void main(String[] args) {
        var scanner = new BufferedScanner();
        var writer = new PrintWriter(new BufferedOutputStream(System.out));

        var n = scanner.nextInt();
        var k = scanner.nextInt();
        var a = new int[n];
        var t = System.nanoTime();
//        if (n == 200000) {
//            System.out.println("a reading begin...");
//        }
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
//            a[i] = (int) (Math.random() * (n / 2) + n / 2);
//            if (n == 200000 && i < 100) {
//                System.out.print(a[i] + " ");
//            }
        }
//        if (n == 200000) {
//            System.out.println();
//            System.out.println("a reading finished: " + (System.nanoTime() - t) / 1e9);
//        }
        writer.println(solve(n, k, a));
        scanner.close();
        writer.flush();
        writer.close();
    }

    private static long solve(int n, int k, int[] a) {
        var t = System.nanoTime();
//        if (n == 200000) {
//            System.out.println("a sort begin...");
//        }
        var tmpA = new ArrayList<Integer>();
        for (int x : a) {
            tmpA.add(x);
        }
        tmpA.sort(Integer::compareTo);
        a = tmpA.stream().mapToInt(i->i).toArray();
//        Arrays.sort(a);
//        if (n == 200000) {
//            System.out.println("a sort finished: " + (System.nanoTime() - t) / 1e9);
//        }
        var acc = new HashMap<Integer, Long>();
        var cnt = new HashMap<Integer, Integer>();
        t = System.nanoTime();
        var orderTmp = new ArrayList<Integer>();
        {
            var tmp = 0L;
            var prev = 0;
            for (int i = 0; i < n; i++) {
                if (i == 0 || a[i] != a[i - 1]) {
                    acc.put(prev, tmp);
                    cnt.put(prev, i);
                    orderTmp.add(prev);
                    prev = a[i];
                }
                tmp += a[i];
            }
            acc.put(prev, tmp);
            cnt.put(prev, n);
            orderTmp.add(prev);
        }
//        if (n == 200000) {
//            System.out.println("acc cnt orderTmp: " + (System.nanoTime() - t) / 1e9);
//        }
        t = System.nanoTime();
        orderTmp.sort(Integer::compareTo);
//        var order = acc.keySet().stream().mapToInt(i -> i).toArray();
        var order = orderTmp.stream().mapToInt(i -> i).toArray();
//        Arrays.sort(order);
//        if (n == 200000) {
//            System.out.println("orderTmp sort, to order: " + (System.nanoTime() - t) / 1e9);
//        }
        var ans = Long.MAX_VALUE;
        for (int i = 1; i < order.length; i++) {
            var target = order[i];
            ans = Math.min(ans, solve(target, a[n - 1], n, k, acc, cnt, order, i));
        }
        return ans;
    }

    private static long solve(int target, int max, int n, int k, Map<Integer, Long> acc, Map<Integer, Integer> cnt,
            int[] order, int whichOrder) {

        var greatestLte = order[whichOrder - 1];
//        var greatestLte = greatestLte(target - 1, order);
        var already = cnt.get(target) - cnt.get(greatestLte);
        if (already >= k) {
            return 0;
        }
        var allOneLessCnt = cnt.get(greatestLte);
        var allOneLess = (long) (target - 1) * allOneLessCnt;
        var allOneLessSteps = allOneLess - acc.get(greatestLte);

        var greatestLte2 = order[whichOrder];
//        var greatestLte2 = greatestLte(target, order);
        var allOneMoreCnt = n - cnt.get(greatestLte2);
        var allOneMore = (long) (target + 1) * allOneMoreCnt;
        var allOneMoreSteps = (acc.get(max) - acc.get(greatestLte2)) - allOneMore;

        var ans = Long.MAX_VALUE;
        // 只使用小的
        if (already + allOneLessCnt >= k) {
            var steps = allOneLessSteps + k - already;
            ans = Math.min(ans, steps);
        }
        // 只使用大的
        if (already + allOneMoreCnt >= k) {
            var steps = allOneMoreSteps + k - already;
            ans = Math.min(ans, steps);
        }
        // 同时使用大的和小的
        var steps = allOneLessSteps + allOneMoreSteps + k - already;
        ans = Math.min(ans, steps);

        return ans;
    }

    private static int greatestLte(int target, int[] order) {
        var k = Arrays.binarySearch(order, target);
        if (k < 0) {
            k = -k - 1;
        }
        return order[k];
    }

    public static class BufferedScanner {
        BufferedReader br;
        StringTokenizer st;

        public BufferedScanner(Reader reader) {
            br = new BufferedReader(reader);
        }

        public BufferedScanner() {
            this(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        void close() {
            try {
                br.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }

    static long gcd(long a, long b) {
        if (a < b) {
            return gcd(b, a);
        }
        while (b > 0) {
            long tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }

    static long inverse(long a, long m) {
        long[] ans = extgcd(a, m);
        return ans[0] == 1 ? (ans[1] + m) % m : -1;
    }

    private static long[] extgcd(long a, long m) {
        if (m == 0) {
            return new long[]{a, 1, 0};
        } else {
            long[] ans = extgcd(m, a % m);
            long tmp = ans[1];
            ans[1] = ans[2];
            ans[2] = tmp;
            ans[2] -= ans[1] * (a / m);
            return ans;
        }
    }

    private static List<Integer> primes(double upperBound) {
        var limit = (int) Math.sqrt(upperBound);
        var isComposite = new boolean[limit + 1];
        var primes = new ArrayList<Integer>();
        for (int i = 2; i <= limit; i++) {
            if (isComposite[i]) {
                continue;
            }
            primes.add(i);
            int j = i + i;
            while (j <= limit) {
                isComposite[j] = true;
                j += i;
            }
        }
        return primes;
    }


}