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 test {
	static int a[];

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);

		int t = 1;// sc.nextInt();

		StringBuilder out = new StringBuilder();
		while (t-- > 0) {

			int n = sc.nextInt();
			long k = sc.nextInt();
			HashMap<Integer, Integer> hm = new HashMap<>();
			for (int i = 1; i <= n; i++) {
				int in = sc.nextInt();

				hm.put(in, hm.getOrDefault(in, 0) + 1);
			}
			pair a[] = new pair[hm.size() + 2];
			int i = 1;
			a[0] = new pair(0, 0);
			a[a.length - 1] = new pair((long) 1e11, 0);
			for (Integer key : hm.keySet()) {
				a[i] = new pair(key, hm.get(key));
				i++;
			}

			Arrays.sort(a);
			TreeMap<Long, Long> tm = new TreeMap<>();
			TreeMap<Long, Long> tms = new TreeMap<>();
			long dpp[] = new long[a.length + 2];
			long dps[] = new long[a.length + 2];
			tm.put((long) 0, (long) 0);
			tms.put((long) 1e11, (long) 0);

			for (i = 1; i < a.length - 1; i++) {
				long val = a[i].val;
				long cnt = a[i].cnt;
				dpp[i] = dpp[i - 1] + (val - a[i - 1].val) * tm.get(a[i - 1].val);
				tm.put(val, tm.get(a[i - 1].val) + cnt);

			}
			for (i = a.length - 2; i > 0; i--) {
				long val = a[i].val;
				long cnt = a[i].cnt;
				dps[i] = dps[i + 1] + (a[i + 1].val - val) * tms.get(a[i + 1].val);
				tms.put(val, tms.get(a[i + 1].val) + cnt);
			}
			long ans = (long) 1e18;
			for (i = 1; i < a.length - 1; i++) {
				long val = a[i].val;
				long cnt = a[i].cnt;
				long rem = Math.max(k - cnt, 0);
				long p = Math.min(rem, tm.get(a[i - 1].val));
				rem = rem - p;
				long s = Math.min(rem, tms.get(a[i + 1].val));
				long cal = p + s;
				cal += p > 0 ? dpp[i - 1] + (a[i].val - a[i - 1].val - 1) * tm.get(a[i - 1].val) : 0;
				cal += s > 0 ? dps[i + 1] + (a[i + 1].val - a[i].val - 1) * tms.get(a[i + 1].val) : 0;
				ans = Math.min(ans, cal);
				rem = Math.max(k - cnt, 0);
				s = Math.min(rem, tms.get(a[i + 1].val));
				rem = rem - s;
				p = Math.min(rem, tm.get(a[i - 1].val));
				cal = p + s;
				cal += p > 0 ? dpp[i - 1] + (a[i].val - a[i - 1].val - 1) * tm.get(a[i - 1].val) : 0;
				cal += s > 0 ? dps[i + 1] + (a[i + 1].val - a[i].val - 1) * tms.get(a[i + 1].val) : 0;
				ans = Math.min(ans, cal);

			}
			out.append(ans + "\n");
		}

		System.out.println(out);
	}

	static class pair implements Comparable<pair> {
		long val;
		long cnt;

		public pair(long i, long j) {
			val = i;
			cnt = j;

		}

		@Override
		public int compareTo(pair o) {
			// TODO Auto-generated method stub
			return (int) (this.val - o.val);

		}

	}

}