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.*;

public class main{
	static int MAX = 100010;
	static long mod = 998244353;
	static ArrayList<Integer>[] amp, bmp;
    static boolean b[];
    static Scanner sc = new Scanner(System.in);
	public static void main(String[] args){
		int n = sc.nextInt(), k = sc.nextInt();
        int arr[] = new int[n];
        for(int i = 0; i< n; i++){
            arr[i] = sc.nextInt();
        }
        int[] fq = new int[4*100000+1000];
        for(int i : arr) fq[i]++;
        int fa = 1000000000;
        int prefix[] = new int[4*100000+1000];
        for(int i = 1; i<prefix.length; i++){
            prefix[i] = prefix[i-1]+fq[i];
        }
        int pow[] = new int[25];
        pow[0] = 1;
        for(int i =1; i<=24; i++) pow[i] = pow[i-1]*2;
        for(int i = 1; i<=2*100000; i++){
            int val = fq[i], temp = i, cnt = i, j = 0, ans = 0, prev = i-1, prev_val = 0;
            while(val < k && cnt < 200010){
                ans += (prefix[cnt] - prefix[temp-1])*j;
                prev_val = val;
                j++;
                temp = i*pow[j];
                cnt = temp + pow[j]-1;
                val += (prefix[cnt] - prefix[temp-1]);
            }
            if(val >= k){
                ans += (k - prev_val)*j;
                fa = Math.min(fa,ans);
            }    
        //System.out.println(val +" "+ans+" "+j);
        }
        System.out.println(fa);
	}

    static long ncp(int k, int x){
        if(k<x) return 0;
        if(k==x) return 1;
        long ans = 1;
        for(int i = k; i>(k-x); i--){
            ans *= i;
            ans %= mod;
        }
        return ans;
    }

    static int dfs(int x){
        b[x] = true;
        int ans = 1;
        for(int i : amp[x]){
            if(!b[i]){
                ans += dfs(i);
            }
        }
        return ans;
    }

    static void buildGraph(int n){
        for(int i=0; i<n; i++){
            int x = sc.nextInt(), y = sc.nextInt(), c = sc.nextInt();
            if (c == 1) {
                bmp[x].add(y);
                bmp[y].add(x);
            }
            else{
                amp[x].add(y);
                amp[y].add(x);
            }
        }
    }

	static long pow(long x, int y, long mod){
		long ans = 1;
		while(y>0){
			if(y%2==0){
				x *= x;
				x %= mod;
				y/=2;
			}
			else{
				y-=1;
				ans *= x;
				ans %= mod;
			}
		}
		return ans;
	}
	static class Pair implements Comparable<Pair>{
		int x, y;
		Pair(int a, int b){
			x = a; y = b;
		}
        public int compareTo(Pair p){
            return -Integer.compare(this.y, p.y);
        }
	}
	public static int[] radixSort(int[] f){ return radixSort(f, f.length); }
	public static int[] radixSort(int[] f, int n)
	{
		int[] to = new int[n];
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(f[i]&0xffff)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[f[i]&0xffff]++] = f[i];
			int[] d = f; f = to;to = d;
		}
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(f[i]>>>16)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[f[i]>>>16]++] = f[i];
			int[] d = f; f = to;to = d;
		}
		return f;
	}

}