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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeSet;
 
public class Main {

	
public static void main(String[] args){
 
   new Thread(null, null, "Anshum Gupta", 99999999) {
        public void run() {
            try {
                solve();
            } catch(Exception e) {
                e.printStackTrace();
                System.exit(1);
            }
        }
    }.start();
}
 
static final long mxx = (long)(1e18 + 5);
static final int mxN = (int)(1e6);
static final int mxV = (int)(1e6), log = 18;
static final long MOD = 998244353; 
static final int INF = (int)1e9;
static boolean[]vis;
static ArrayList<ArrayList<Integer>> adj;
static int n, m, q, k;
static char[]str;

public static void solve() throws Exception {
	   // solve the problem here
		s = new MyScanner();
   		out = new PrintWriter(new BufferedOutputStream(System.out), true);
//	   		out = new PrintWriter("output.txt");
        int tc = 1;//s.nextInt();
        for(int i=1; i<=tc; i++) {
//        	out.print("Case #" + i + ": ");
        	testcase();
        }
           
        out.flush();
        out.close();
}




static void testcase() {
	n = s.nextInt();
	long k = s.nextLong();
	int[] a = s.nextIntArray(n);
	shuffleSort(a);
	HashMap<Integer, Long> prefixDp = new HashMap<>(), suffixDp = new HashMap<>();
	long moves = mxx;
	for(int i = 0; i < n; ) {
		int j = i + 1;
		while(j < n && a[j] == a[i]) 
			j++;
		if(i == 0) {
			prefixDp.put(a[i], 0L);
		} else {
			long prev = prefixDp.get(a[i - 1]);
			long cur = prev + 1L * (a[i] - a[i - 1]) * i;
			prefixDp.put(a[i], cur);
		}
		i = j;
	}
	
	for(int i = n - 1; i >= 0;  ) {
		int j = i - 1;
		while(j >= 0 && a[j] == a[i]) 
			j--;
		if(i == n - 1) {
			suffixDp.put(a[i], 0L);
		} else {
			long prev = suffixDp.get(a[i + 1]);
			long cur = prev + 1L * (a[i + 1] - a[i]) * (n - i - 1);
			suffixDp.put(a[i], cur);
		}
		i = j;
	}
	
	for(int i = 0; i < n; ) {
		int j = i + 1;
		while(j < n && a[j] == a[i])
			j++;
		long times = j - i;
//		out.println("i = " + i +  " times = " + times);
		if(times >= k) {
			moves = 0;
		}else {
			// find cost of turning prefix into (a[i] - 1)
			long prefixCost = i == 0 ? 0 : prefixDp.get(a[i - 1]) + 1L * (a[i] - 1L - a[i - 1]) * i;
			
			// cost of suffix
			long suffixCost = j == n ? 0 : suffixDp.get(a[j]) + 1L * (a[j] - a[i] - 1L) * (n - j);
			
			// only prefix is good
			if(times + i >= k) {
				moves = Math.min(moves, prefixCost + k - times);
			}
			
			if(times + n - j >= k) {
				moves = Math.min(moves, suffixCost + k - times);
			}
			
			moves = Math.min(moves, prefixCost + suffixCost + k - times);
		}
//		out.println("i = " + i + " moves = " + moves);
		i = j;
	}
	
	out.println(moves);
}


public static PrintWriter out;
public static MyScanner s;
static void shuffleArray(int[] a) {
	Random random = new Random();
	for (int i = a.length-1; i > 0; i--) {
		int index = random.nextInt(i + 1);
		int tmp = a[index];
		a[index] = a[i];
		a[i] = tmp;
	}
}
static void shuffleSort(int[] a) {
	shuffleArray(a);
	Arrays.parallelSort(a);
}
static class MyScanner {
 
    BufferedReader br;
    StringTokenizer st;
 
    public MyScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    public MyScanner(String fileName) {
    	try {
			br = new BufferedReader(new FileReader(fileName));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
    }
    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()); }
    int[] nextIntArray(int n){
    	int[]a = new int[n];
    	for(int i=0; i<n; i++) {
    		a[i] = this.nextInt();
    	}
    	return a;
    }
    long[] nextlongArray(int n) {
    	long[]a = new long[n];
    	for(int i=0; i<n; i++) {
    		a[i] = this.nextLong();
    	}
    	return a;
    }
    Integer[] nextIntegerArray(int n){
    	Integer[]a = new Integer[n];
    	for(int i=0; i<n; i++) {
    		a[i] = this.nextInt();
    	}
    	return a;
    }
    Long[] nextLongArray(int n) {
    	Long[]a = new Long[n];
    	for(int i=0; i<n; i++) {
    		a[i] = this.nextLong();
    	}
    	return a;
    }
    char[][] next2DCharArray(int n, int m){
    	char[][]arr = new char[n][m];
    	for(int i=0; i<n; i++) {
    		arr[i] = this.next().toCharArray();
    	}
    	return arr;
    }
    ArrayList<ArrayList<Integer>> readUndirectedUnweightedGraph(int n, int m) {
    	ArrayList<ArrayList<Integer>>adj = new ArrayList<ArrayList<Integer>>();
    	for(int i=0; i<=n; i++)adj.add(new ArrayList<Integer>());
    	for(int i=0; i<m; i++) {
    		int u = s.nextInt();
    		int v = s.nextInt();
    		adj.get(u).add(v);
    		adj.get(v).add(u);
    	}
    	return adj;
    }
    ArrayList<ArrayList<Integer>> readDirectedUnweightedGraph(int n, int m) {
    	ArrayList<ArrayList<Integer>>adj = new ArrayList<ArrayList<Integer>>();
    	for(int i=0; i<=n; i++)adj.add(new ArrayList<Integer>());
    	for(int i=0; i<m; i++) {
    		int u = s.nextInt();
    		int v = s.nextInt();
    		adj.get(u).add(v);
    	}
    	return adj;
    }
    String nextLine(){
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}
 
 
}