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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int n, k;
int arr[51], nm[2 * 100001];
map<int, int> st[2 * 100001];
int main() {
  cin.sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> k;
  int maxnmb = -1;
  int minc = INT_MAX;
  for (int i = 0; i < n; ++i) {
    cin >> arr[i];
    ++nm[arr[i]];
    if (nm[arr[i]] >= k) minc = 0;
    if (arr[i] > maxnmb) maxnmb = arr[i];
  }
  for (int i = maxnmb; i >= 1; --i) {
    if (nm[i] == 0) continue;
    int rate = 1;
    int nmb = i;
    while (nmb != 0) {
      st[nmb >> 1][rate] += nm[i];
      nmb >>= 1;
      ++rate;
    }
  }
  for (int i = 0; i < maxnmb; ++i) {
    int rem = k - nm[i];
    if (rem < 0) rem = 0;
    int cost = 0;
    for (auto j : st[i]) {
      cost += min(rem, j.second) * j.first;
      rem -= j.second;
      if (rem <= 0) break;
    }
    if (rem > 0) continue;
    minc = min(minc, cost);
  }
  cout << minc;
  return 0;
}