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.concurrent.TimeUnit;

public class f629 implements Runnable{
	
    public static void main(String[] args) {
    	try{
            new Thread(null, new f629(), "process", 1<<26).start();
        }
        catch(Exception e){
            System.out.println(e);
        }
    }
	public void run() {
		FastReader scan = new FastReader();
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		//PrintWriter out = new PrintWriter("file.out");
		Task solver = new Task();
		//int t = scan.nextInt();
		int t = 1;
		for(int i = 1; i <= t; i++) solver.solve(i, scan, out);
		out.close();
	}

	static class Task {

		public void solve(int testNumber, FastReader sc, PrintWriter out) {
			int N = sc.nextInt();
			int K = sc.nextInt();

			PriorityQueue<Integer> front = new PriorityQueue<>();
			PriorityQueue<Integer> back = new PriorityQueue<>(Collections.reverseOrder());

			TreeMap<Long, Long> next = new TreeMap<>();
			long start = 0;
			for(int i = 0; i < N; i++) {
				int x = sc.nextInt();
				if(start == 0)
					start = x;
				if(start == 561987393)
					x-=561986000;
				front.add(x);
				back.add(x);
				if(!next.containsKey((long)x)){
					next.put((long)x, 0l);
				}
				next.put((long)x, next.get((long)x)+1);
			}
			//if(start == 561987393)
			//	System.out.println(next);
			long curEqFront = 1;
			long curFront = front.poll();
			long frontMoves = 0;
			
			long curEqBack = 1;
			long curBack = back.poll();
			long backMoves = 0;
			
			long min = Long.MAX_VALUE;

			if(curEqFront == K || curEqBack == K) {
				out.println(0);
				out.close();
				System.exit(0);
			}
			Map<Long, tup> storage = new HashMap<>();
			Map<Long, tup> storage2 = new HashMap<>();
			storage.put(curFront, new tup(frontMoves, curEqFront));
			storage2.put(curBack, new tup(backMoves, curEqBack));

			while(front.size() > 0 || back.size() > 0) {
				long frCost = (curEqFront) * (front.peek() - curFront);
				long bCost = (curEqBack) * (curBack - back.peek());
				
				curEqFront++;
				frontMoves += frCost;
				curFront = front.poll();
				storage.put(curFront, new tup(frontMoves, curEqFront));
				curEqBack++;
				backMoves += bCost;
				curBack = back.poll();
				storage2.put(curBack, new tup(backMoves, curEqBack));
				
				if(curEqFront == K) {
					long extra = 0;
					while(front.size() > 0 && front.peek() == curFront) {
						front.poll();
						extra++;
					}
					min = Math.min(min, frontMoves - extra);
					while(extra > 0) {
						front.add((int)curFront);
						extra--;
					}
					//break;
				}
				if(curEqBack == K) {
					//System.out.println(backMoves);
					long extra = 0;
					while(back.size() > 0 && back.peek() == curBack) {
						back.poll();
						extra++;
					}
					min = Math.min(min, backMoves - extra);
					while(extra > 0) {
						back.add((int)curBack);
						extra--;
					}
					//break;
				}
			}

			//if(start == 561987393)
			//	System.out.println(min);
			//System.out.println(min);
			//System.out.println(storage);
			//System.out.println(storage2);
			
			for(long cur: storage.keySet()) {
				long extra = K - next.get(cur);
				if(extra <= 0) {
					min = 0;
					break;
				}
				if(next.higherKey(cur) != null && next.lowerKey(cur) != null) {
					long lo = next.lowerKey(cur);
					long hi = next.higherKey(cur);
					
					long cost1 = Long.MAX_VALUE;
					if(storage.get(lo).b < extra) {
						cost1 = storage.get(lo).a + storage2.get(hi).a + (storage.get(lo).b) * (cur - lo) + (extra-(storage.get(lo).b)) + storage2.get(hi).b * (hi - cur - 1);
					}
					long cost2 = Long.MAX_VALUE;
					if(storage2.get(hi).b < extra) {
						cost2 = storage.get(lo).a + storage2.get(hi).a + (storage2.get(hi).b) * (hi - cur) + (extra - (storage2.get(hi).b)) + storage.get(lo).b * (cur - lo - 1);
					}
					
					min = Math.min(min, Math.min(cost1, cost2));
					
				}
			}
			out.println(min);
		}
	}
	static long binpow(long a, long b, long m) {
		a %= m;
		long res = 1;
		while (b > 0) {
			if ((b & 1) == 1)
				res = res * a % m;
			a = a * a % m;
			b >>= 1;
		}
		return res;
	}
	static void sort(int[] x){
		shuffle(x);
		Arrays.sort(x);
	}
	static void sort(long[] x){
		shuffle(x);
		Arrays.sort(x);
	}
	static class tup implements Comparable<tup>, Comparator<tup>{
		long a, b;
		tup(long a,long b){
			this.a=a;
			this.b=b;
		}
		public tup() {
		}
		@Override
		public int compareTo(tup o){
			return Long.compare(o.b,b);
		}
		@Override
		public int compare(tup o1, tup o2) {
			return Long.compare(o1.b, o2.b);
		}
		
		@Override
	    public int hashCode() {
			return Objects.hash(a, b);
	    }
 
	    @Override
	    public boolean equals(Object obj) {
	    	if (this == obj)
                return true;
	    	if (obj == null)
                return false;
	    	if (getClass() != obj.getClass())
                return false;
	    	tup other = (tup) obj;
	    	return a==other.a && b==other.b;
	    }
	    
	    @Override
	    public String toString() {
	    	return a + " " + b;
	    }
	}
	
	static void shuffle(int[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			int temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}

	static void shuffle(long[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			long temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}

		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;
		}
	}

}