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 MakeKEqual {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(in.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		Integer[] a = new Integer[N];
		st = new StringTokenizer(in.readLine());
		for(int i = 0; i < N; ++i) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		long ans = solve(a, N, K);
		out.println(ans);
		in.close();
		out.close();
	}
	public static long solve(Integer[] a, int N, int K) {
		Arrays.sort(a);
		int[] val = new int[N];
		int[] cnt = new int[N];
		int idx = 0;
		for(int i = 0; i < N; ++i) {
			if(i > 0 && a[i] > a[i - 1]) {
				idx++;
			}
			cnt[idx]++;
			val[idx] = a[i];
		}
		long[] bringUpMin = new long[idx + 1];
		int[] totBefore = new int[idx + 1];
		totBefore[0] = cnt[0];
		for(int i = 1; i <= idx; ++i) {
			bringUpMin[i] = bringUpMin[i - 1] + (long)totBefore[i - 1] * (long)(val[i] - val[i - 1]);
			totBefore[i] = totBefore[i - 1] + cnt[i];
		}
		long[] bringDownMax = new long[idx + 1];
		int[] totAfter = new int[idx + 1];
		totAfter[idx] = cnt[idx];
		for(int i = idx - 1; i >= 0; --i) {
			bringDownMax[i] = bringDownMax[i + 1] + (long)totAfter[i + 1] * (long)(val[i + 1] - val[i]);
			totAfter[i] = totAfter[i + 1] + cnt[i];
		}
		long ans = Long.MAX_VALUE;
		for(int i = 0; i <= idx; ++i) {
			if(cnt[i] >= K) {
				ans = 0;
				break;
			}
			if(totBefore[i] >= K) {
				ans = Math.min(ans, bringUpMin[i] - (totBefore[i] - K));
			}
			if(totAfter[i] >= K) {
				ans = Math.min(ans, bringDownMax[i] - (totAfter[i] - K));
			}
			ans = Math.min(ans, bringUpMin[i] + bringDownMax[i] - (N - K));
		}
		return ans;
	}
	public static long min(long a, long b) {
		return a < b ? a : b;
	}
	public static long max(long a, long b) {
		return a > b ? a : b;
	}
}