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.*;

public class Problem_F {
	static final long INF = Long.MAX_VALUE / 2;

	public static void shuffle(long[] A) {
		for (int i = 0; i < A.length; i++) {
			int j = (int)(i * Math.random());
			long tmp = A[i];
			A[i] = A[j];
			A[j] = tmp;
		}
	}

	public static void main(String[] args) {
		InputReader in = new InputReader();

		int N = in.nextInt();
		int K = in.nextInt();
		long[] A = new long[N];
		for (int i = 0; i < N; i++) {
			A[i] = in.nextInt();
		}
		shuffle(A);
		Arrays.sort(A);
		int[] B = new int[N];
		int[] C = new int[N];
		long[] D = new long[N];
		long[] E = new long[N];
		for (int i = 1; i < N; i++) {
			B[i] = A[i] == A[i - 1] ? B[i - 1] : i;
			D[i] = D[i - 1] + (A[i] - A[i - 1]) * i;
		}
		C[N - 1] = N - 1;
		for (int i = N - 2; i >= 0; i--) {
			C[i] = A[i] == A[i + 1] ? C[i + 1] : i;
			E[i] = E[i + 1] + (A[i + 1] - A[i]) * (N - 1 - i);
		}
		long ans = INF;
		for (int i = 0; i < N; i++) {
			if (B[i] < i) {
				continue;
			}
			int x = C[i] - B[i] + 1;
			if (x >= K) {
				ans = 0;
				break;
			}
			x = K - x;
			if (x <= B[i]) {
				ans = Math.min(ans, D[i - 1] + (A[i] - A[i - 1] - 1) * i + x);
			}
			if (x <= N - C[i] - 1) {
				ans = Math.min(ans, E[C[i] + 1] + (A[C[i] + 1] - A[C[i]] - 1) * (N - C[i] - 1) + x);
			}
			ans = Math.min(ans, (i > 0 ? D[i - 1] + (A[i] - A[i - 1] - 1) * i : 0)
					+ (C[i] + 1 < N ? E[C[i] + 1] + (A[C[i] + 1] - A[C[i]] - 1) * (N - C[i] - 1) : 0) + x);
		}

		System.out.println(ans);
	}

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

		public InputReader() {
			reader = new BufferedReader(new InputStreamReader(System.in));
		}

		public String next() {
			while (st == null || !st.hasMoreTokens()) {
				st = new StringTokenizer(nextLine());
			}
			return st.nextToken();
		}

		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return null;
		}

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