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:
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x1328F
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int K = Integer.parseInt(st.nextToken());
         int[] arr = new int[N];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
         sort(arr);
         if(triv(arr, K))
            System.out.println(0);
         else
         {
            long res = Long.MAX_VALUE;
            ArrayList<Integer> ls = new ArrayList<Integer>();
            ls.add(arr[0]);
            for(int i=1; i < N; i++)
               if(ls.get(ls.size()-1) != arr[i])
                  ls.add(arr[i]);
            //psums bad
            HashMap<Integer, Integer> left = new HashMap<Integer, Integer>();
            HashMap<Integer, Integer> right = new HashMap<Integer, Integer>();
            for(int i=0; i < N; i++)
            {
               if(!left.containsKey(arr[i]))
                  left.put(arr[i], i+1);
               right.put(arr[i], i+1);
            }
            FenwickTree bit = new FenwickTree(N+4);
            for(int i=0; i < N; i++)
               bit.add(i+1, arr[i]);
            for(int curr: ls)
            {
               int a = left.get(curr);
               int b = right.get(curr);
               long lhs = bit.query(1, a-1);
               long rhs = bit.query(b+1, N);
               int extra = K-(b-a+1);
               //casework
               long cost1 = (long)(curr-1)*(a-1);
               long cost2 = (long)(curr+1)*(N-b);
               cost1 -= lhs;
               cost2 = rhs-cost2;
               res = Math.min(res, cost1+cost2+extra);
               if(a-1 >= extra)
                  res = Math.min(res, cost1+extra);
               if(N-b >= extra)
                  res = Math.min(res, cost2+extra);
            }
            System.out.println(res);
         }
      }
      public static boolean triv(int[] arr, int K)
      {
         int cnt = 1;
         int tag = arr[0];
         for(int i=1; i < arr.length; i++)
         {
            if(tag == arr[i])
               cnt++;
            else
            {
               if(cnt >= K)
                  return true;
               cnt = 1;
               tag = arr[i];
            }
         }
         return cnt >= K;
      }
      public static void sort(int[] arr)
      {
         //stable heap sort
         PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
         for(int a: arr)
            pq.add(a);
         for(int i=0; i < arr.length; i++)
            arr[i] = pq.poll();
      }
   }
   class FenwickTree
   {
      //1 indexed
      public long[] tree;
      public int size;
      
      public FenwickTree(int size)
      {
         this.size = size;
         tree = new long[size+5];
      }
      public void add(int i, int v)
      {
         while(i <= size)
         {
            tree[i] += v;
            i += i&-i;
         }
      }
      public long find(int i)
      {
         long res = 0L;
         while(i >= 1)
         {
            res += tree[i];
            i -= i&-i;
         }
         return res;
      }
      public long query(int l, int r)
      {
         return find(r)-find(l-1);
      }
   }