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

public class Main {

	static class Task {

		int NN = 200005;
		int MOD = 1000000007;
		int INF = 2000000000;
		long INFINITY = 2000000000000000000L;

		public void solve(InputReader in, PrintWriter out) {
      int n = in.nextInt();
      int k = in.nextInt();
      Map<Integer, Integer> mp = new HashMap<>();
      List<Integer> d = new ArrayList<>();
      for(int i=0;i<n;++i){
        int x = in.nextInt();
        int cnt = 0;
        if(mp.containsKey(x))
          cnt = mp.get(x);
        ++cnt;
        if(cnt == 1) {
          d.add(x);
        }
        mp.put(x, cnt);
      }
      Collections.sort(d);
      List<Long> sl = new ArrayList<>();
      List<Long> sr = new ArrayList<>();
      List<Long> cl = new ArrayList<>();
      List<Long> cr = new ArrayList<>();
      long sum = 0;long cnt = 0;
      for(int num: d) {
        sum += 1L * mp.get(num) * num;
        cnt += 1L * mp.get(num);
        sl.add(sum);
        cl.add(cnt);
      }
      sum = 0;
      cnt = 0;
      for(int i=d.size() - 1;i>=0;--i) {
        int num = d.get(i);
        sum += 1L * mp.get(num) * num;
        cnt += 1L * mp.get(num);
        sr.add(sum);
        cr.add(cnt);
      }
      long ans = -1;
      for(int i=0;i<d.size();++i) {
        int cur = d.get(i);
        int prev = cur - 1;
        int next = cur + 1;
        long totall = 0;
        long totalr = 0;
        if(i+1 < d.size()) {
          totalr = sr.get(d.size() - 1 - i - 1) - 1L*cr.get(d.size() - 1 - i - 1)*next;
        }
        if(i > 0) {
          totall = 1L*cl.get(i - 1)*prev - sl.get(i - 1);
        }
        int curCount = mp.get(cur);
        if(curCount >= k){
          ans = 0;break;
        }
        long need = k - curCount;
        long total = need + totall + totalr;
        if(i > 0 && cl.get(i - 1) >= need) {
          total = Math.min(total, totall + need);
        }
        if(i + 1 < d.size() && cr.get(d.size() - 1 - i - 1) >= need) {
          total = Math.min(total, totalr + need);
        }
        if(ans == -1){
          ans = total;
        } else {
          ans = Math.min(ans, total);
        }
      }
      out.println(ans);
    }

	}

	static void prepareIO(boolean isFileIO) {
		//long t1 = System.currentTimeMillis();
		Task solver = new Task();
		// Standard IO
		if(!isFileIO) {
			InputStream inputStream = System.in;
      OutputStream outputStream = System.out;
      InputReader in = new InputReader(inputStream);
      PrintWriter out = new PrintWriter(outputStream);
      solver.solve(in, out);
      //out.println("time(s): " + (1.0*(System.currentTimeMillis()-t1))/1000.0);
      out.close();
		}
    // File IO
		else {
			String IPfilePath = System.getProperty("user.home") + "/Downloads/ip.in";
      String OPfilePath = System.getProperty("user.home") + "/Downloads/op.out";
      InputReader fin = new InputReader(IPfilePath);
      PrintWriter fout = null;
      try {
				fout = new PrintWriter(new File(OPfilePath));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
      solver.solve(fin, fout);
      //fout.println("time(s): " + (1.0*(System.currentTimeMillis()-t1))/1000.0);
      fout.close();
		}
	}

	public static void main(String[] args) {
        prepareIO(false);
	}

	static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public InputReader(String filePath) {
        	File file = new File(filePath);
            try {
				reader = new BufferedReader(new FileReader(file));
			} catch (FileNotFoundException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
            tokenizer = null;
        }

        public String nextLine() {
        	String str = "";
        	try {
				str = reader.readLine();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
        	return str;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

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

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

    }

}