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

public class round582d3d1 {

	public static void main(String args[]) {
		FastScanner in = new FastScanner(System.in);
		
		int[][] arr = new int[200001][30];
		int n = in.nextInt();
		int k = in.nextInt();
		for (int i = 0; i < n; i++) {
			int input = in.nextInt();
			int count = 0;
			arr[input][count]++;
			while (input > 0) {
				input /= 2;
				count++;
				arr[input][count]++;
				
			}
		}
		//System.out.println(Arrays.deepToString(arr));
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < 200001; i++) {
			int[] row = arr[i];
			int count = 0;
			int ops = 0;
			for (int j = 0; j < 30; j++) {
				count += row[j];
				ops += j*row[j];
				if (count >= k) {
					count -= row[j];
					ops -= j*row[j];
					//count += (k-count);
					ops += j*(k-count);
					min = Integer.min(min, ops);
					break;
				}
			}
		}
		System.out.println(min);

	}

	// ======================================================================================
	// =============================== Reference Code =======================================
	// ======================================================================================

	static int greatestDivisor(int n) {
		int limit = (int) Math.sqrt(n);
		int max = 1;
		for (int i = 2; i <= limit; i++) {
			if (n % i == 0) {
				max = Integer.max(max, i);
				max = Integer.max(max, n / i);
			}
		}
		return max;
	}

	// Method to return all primes smaller than or equal to 
	// n using Sieve of Eratosthenes 
	static boolean[] sieveOfEratosthenes(int n) {
		// Create a boolean array "prime[0..n]" and initialize 
		// all entries it as true. A value in prime[i] will 
		// finally be false if i is Not a prime, else true. 
		boolean prime[] = new boolean[n + 1];
		for (int i = 0; i <= n; i++)
			prime[i] = true;

		prime[0] = false;
		prime[1] = false;

		for (int p = 2; p * p <= n; p++) {
			// If prime[p] is not changed, then it is a prime 
			if (prime[p] == true) {
				// Update all multiples of p 
				for (int i = p * p; i <= n; i += p)
					prime[i] = false;
			}
		}

		return prime;
	}

	// Binary search for number greater than or equal to target
	// returns -1 if number not found
	private static int bin_gteq(int[] a, int key) {
		int low = 0;
		int high = a.length;
		int max_limit = high;
		while (low < high) {
			int mid = low + (high - low) / 2;
			if (a[mid] < key) {
				low = mid + 1;
			} else
				high = mid;
		}

		return high == max_limit ? -1 : high;
	}

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

		return gcd(b % a, a);
	}

	static class Tuple<X, Y> {
		public final X x;
		public final Y y;

		public Tuple(X x, Y y) {
			this.x = x;
			this.y = y;
		}

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

	static class Tuple3<X, Y, Z> {
		public final X x;
		public final Y y;
		public final Z z;

		public Tuple3(X x, Y y, Z z) {
			this.x = x;
			this.y = y;
			this.z = z;
		}

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

	static Tuple3<Integer, Integer, Integer> gcdExtended(int a, int b, int x, int y) {
		// Base Case 
		if (a == 0) {
			x = 0;
			y = 1;
			return new Tuple3(0, 1, b);
		}

		int x1 = 1, y1 = 1; // To store results of recursive call 
		Tuple3<Integer, Integer, Integer> tuple = gcdExtended(b % a, a, x1, y1);
		int gcd = tuple.z;
		x1 = tuple.x;
		y1 = tuple.y;

		// Update x and y using results of recursive 
		// call 
		x = y1 - (b / a) * x1;
		y = x1;

		return new Tuple3(x, y, gcd);
	}

	// Returns modulo inverse of a  
	// with respect to m using extended 
	// Euclid Algorithm. Refer below post for details: 
	// https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/ 
	static int inv(int a, int m) {
		int m0 = m, t, q;
		int x0 = 0, x1 = 1;

		if (m == 1)
			return 0;

		// Apply extended Euclid Algorithm 
		while (a > 1) {
			// q is quotient 
			q = a / m;

			t = m;

			// m is remainder now, process 
			// same as euclid's algo 
			m = a % m;
			a = t;

			t = x0;

			x0 = x1 - q * x0;

			x1 = t;
		}

		// Make x1 positive 
		if (x1 < 0)
			x1 += m0;

		return x1;
	}

	// k is size of num[] and rem[]. 
	// Returns the smallest number 
	// x such that: 
	// x % num[0] = rem[0], 
	// x % num[1] = rem[1], 
	// .................. 
	// x % num[k-2] = rem[k-1] 
	// Assumption: Numbers in num[] are pairwise  
	// coprime (gcd for every pair is 1) 
	static int findMinX(int num[], int rem[], int k) {
		// Compute product of all numbers 
		int prod = 1;
		for (int i = 0; i < k; i++)
			prod *= num[i];

		// Initialize result 
		int result = 0;

		// Apply above formula 
		for (int i = 0; i < k; i++) {
			int pp = prod / num[i];
			result += rem[i] * inv(pp, num[i]) * pp;
		}

		return result % prod;
	}

	/**
	 * Source: Matt Fontaine
	 */
	static class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int chars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
		}

		int read() {
			if (chars == -1)
				throw new InputMismatchException();
			if (curChar >= chars) {
				curChar = 0;
				try {
					chars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (chars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

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

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}

}