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

public class dsu {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		Long a[] = new Long[n];
		st = new StringTokenizer(br.readLine());
		HashMap<Long, Integer> h = new HashMap<>();
		for (int i = 0; i < a.length; i++) {
			a[i] = Long.parseLong(st.nextToken());
			h.put(a[i], h.getOrDefault(a[i], 0) + 1);
			if (h.get(a[i]) >= k) {
				System.out.println(0);
				return;
			}
		}
		Arrays.sort(a);
		long b[] = new long[n];
		b[0] = a[0];
		for (int i = 1; i < b.length; i++) {
			b[i] = a[i] + b[i - 1];
		}
		int start = 0;
		int end = 0;
		long min = Long.MAX_VALUE;
		for (int i = 0; i < b.length; i++) {
			end = i;
			if (i < n - 1 && a[i] == a[i + 1]) {
				end = i;
			} else {
				int len = k - (end - start + 1);
				long low = Long.MAX_VALUE;
				long hi = Long.MAX_VALUE;
				if (start > 0) {
					low = (a[start] - 1) * (start) - b[start - 1];
					// System.out.println(low + " " + start + " " + end + len);
				}
				if (end < n - 1) {
					hi = b[n - 1] - b[end] - (a[end] + 1) * (n - end - 1);
					// System.out.println(hi + " " + start + " " + end + " ds " + len);
				}
				long ans = len;
				if (len > start && len > n - end-1) {
					ans += low + hi;
				} else {
					if (len <= start) {
						if (len <= n-end-1) {
							if (hi > low)
								ans += low;
							else
								ans += hi;
						} else {
							ans += low;
						}
					} else
						ans += hi;
				}
				start = i + 1;
				end = i + 1;
				if (ans < min)
					min = ans;
			}
		}
		pw.print(min);
		pw.flush();
	}

	static int gcd(int a, int b) {
		if (b == 0)
			return a;
		return gcd(b, a % b);
	}

	static class pair implements Comparable<pair> {
		int x;
		int y;

		pair(int r, int t) {
			x = r;
			y = t;
		}

		public String toString() {
			return "(" + x + "," + y + ")";
		}

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

	}

	static long power(long x, long y, int p) {

		// Initialize result
		long res = 1;

		// Update x if it is more than or
		// equal to p
		x = x % p;

		while (y > 0) {

			// If y is odd, multiply x
			// with result
			if (y % 2 == 1)
				res = (res * x) % p;

			// y must be even now
			y = y >> 1; // y = y/2
			x = (x * x) % p;
		}

		return res;
	}

	// Returns n^(-1) mod p
	static long modInverse(long n, int p) {
		return power(n, p - 2, p);
	}

	// Returns nCr % p using Fermat's
	// little theorem.
	static long nCrModPFermat(int n, int r, int p) {

		// Base case
		if (r == 0)
			return 1;

		// Fill factorial array so that we
		// can find all factorial of r, n
		// and n-r
		long[] fac = new long[n + 1];
		fac[0] = 1;

		for (int i = 1; i <= n; i++)
			fac[i] = (fac[i - 1] * i) % p;

		return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;
	}

	static int longestPrefixSuffix(String s) {
		int pi[] = new int[s.length()];
		pi[0] = 0;
		char c[] = s.toCharArray();
		for (int i = 1; i < pi.length; i++) {
			int l = pi[i - 1];
			while (l > 0 && c[i] != c[l]) {
				l = pi[l - 1];
			}
			if (c[i] == c[l]) {
				l++;
			}
			pi[i] = l;
		}
		return (pi[c.length - 1]);
	}

}