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.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class B {

	static PrintWriter pw = new PrintWriter(System.out);
	public static void main(String[] args) throws Exception{
			BufferedReader bf= new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st;

			st=new StringTokenizer(bf.readLine());
			int n=Integer.parseInt(st.nextToken());
			int k=Integer.parseInt(st.nextToken());
			int[] arr= new int[n];
			st=new StringTokenizer(bf.readLine());
			PriorityQueue<Pair> pq =new PriorityQueue<>(Collections.reverseOrder());
			HashMap<Integer,Integer> map =new HashMap<>();
			HashMap<Integer,ArrayList<Integer>> numOp =new HashMap<>();
			for(int i=0;i<n;i++) {
				arr[i]=Integer.parseInt(st.nextToken());
				pq.add(new Pair(arr[i],0));
				map.put(arr[i],map.getOrDefault(arr[i], 0)+1);
				if(!numOp.containsKey(arr[i]))
				numOp.put(arr[i],new ArrayList<>());
				numOp.get(arr[i]).add(0);
				if(map.get(arr[i])==k) {
					pw.println(0);
					pw.flush();
					return;
				}
			}
			TreeSet<Integer> op=new TreeSet<>();
			
			for(int i=0;i<n;i++) {
				int num=arr[i];
				int cost=0;
				while(num!=0) {
					num/=2;
					cost++;
					ArrayList<Integer> l=numOp.getOrDefault(num, new ArrayList<Integer>());
					l.add(cost);
					numOp.put(num, l);
				}
			}
			int ans=Integer.MAX_VALUE;
			for(Entry e:numOp.entrySet()) {
				ArrayList<Integer> list=(ArrayList<Integer>) e.getValue();
				if(list.size()<k)
					continue;
				Collections.sort(list);
				int tmp=0;
				for(int i=0;i<k;i++)
					tmp+=list.get(i);
			
				ans=Math.min(ans, tmp);
			}
			pw.println(ans);
//			while(!pq.isEmpty()) {
//				Pair p =pq.poll();
//				int num=p.a;
//				int operation=p.b;
//				num/=2;
//				operation++;
//				map.put(num, map.getOrDefault(num, 0)+1);
//				
//				numOp.put(num, numOp.getOrDefault(num, 0)+operation);
//				
//				if(map.get(num)==k) {
//					op.add(numOp.get(num));
//				}
//				
//				if(num!=0)
//					pq.add(new Pair(num, operation));
//				
//			}
//			pw.println(op.first());
			pw.flush();
	}
	static class Pair implements Comparable<Pair>{
		int a,b;
		public Pair(int x,int y)
		{
			a=x;b=y;
		}
		@Override
		public int compareTo(Pair o) {
			// TODO Auto-generated method stub
		if(a!=o.a)
			return a-o.a;
		return o.b-b;
		}
	}
	static final double EPS=1e-6;
static int log(int a ,int b) {
if(a<b)return (int)1e9;
if(a==b)return 0;
int ans=0;
while(a>b) {
	a/=2;
	ans++;
	if(a==b)
		return ans;;
}
return (int)1e9;

}
}