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:
// upsolve with kaiboy
import java.io.*;
import java.util.*;

public class CF1328F extends PrintWriter {
	CF1328F() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1328F o = new CF1328F(); o.main(); o.flush();
	}

	Random rand = new Random();
	void sort(int[] aa, int n) {
		for (int i = 0; i < n; i++) {
			int j = rand.nextInt(i + 1);
			int tmp = aa[i]; aa[i] = aa[j]; aa[j] = tmp;
		}
		Arrays.sort(aa, 0, n);
	}
	void main() {
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] aa = new int[n];
		for (int i = 0; i < n; i++)
			aa[i] = sc.nextInt();
		sort(aa, n);
		int n_ = n * 3;
		int[] aa_ = new int[n_];
		int[] cc_ = new int[n_];
		n_ = 0;
		for (int i = 0, j; i < n; i = j) {
			j = i + 1;
			while (j < n && aa[j] == aa[i])
				j++;
			if (j - i >= k) {
				println(0);
				return;
			}
			if (i > 0 && aa[i] - aa[i - 1] > 1) {
				int a = aa[i - 1] + 1;
				int b = aa[i] - 1;
				aa_[n_] = a; cc_[n_] = 0; n_++;
				if (a < b) {
					aa_[n_] = b; cc_[n_] = 0; n_++;
				}
			}
			aa_[n_] = aa[i]; cc_[n_] = j - i; n_++;
		}
		n = n_;
		int[] pc = new int[n];
		int[] qc = new int[n];
		long[] ps = new long[n];
		long[] qs = new long[n];
		long s = 0; int c = 0;
		for (int i = 0; i < n; i++) {
			pc[i] = c;
			ps[i] = s;
			c += cc_[i];
			s += (long) aa_[i] * cc_[i];
		}
		s = c = 0;
		for (int i = n - 1; i >= 0; i--) {
			qc[i] = c;
			qs[i] = s;
			c += cc_[i];
			s += (long) aa_[i] * cc_[i];
		}
		long ans = (long) 3e14;
		for (int i = 0; i < n; i++) {
			int a = aa_[i];
			c = k - cc_[i];
			long p = (long) pc[i] * (a - 1) - ps[i];
			long q = qs[i] - (long) qc[i] * (a + 1);
			ans = Math.min(ans, p + q + c);
			if (pc[i] >= c)
				ans = Math.min(ans, p + c);
			if (qc[i] >= c)
				ans = Math.min(ans, q + c);
		}
		println(ans);
	}
}