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;
const long long MAXN = 200100, INF = 0x3f3f3f3f3f3f3f3f;
long long n, k, v[MAXN], pfxcnt[MAXN], pfxsum[MAXN], sfxcnt[MAXN], sfxsum[MAXN],
    ans = INF;
vector<pair<long long, long long>> a;
signed main() {
  scanf("%lld %lld", &n, &k);
  for (long long i = 1; i <= n; i++) scanf("%lld", &v[i]);
  sort(v + 1, v + 1 + n);
  for (long long i = 1, cnt = 0; i <= n + 1; i++) {
    if (i != 1 && v[i] != v[i - 1]) a.emplace_back(v[i - 1], cnt), cnt = 0;
    cnt++;
  }
  pfxcnt[0] = a[0].second, pfxsum[0] = a[0].first * a[0].second;
  for (long long i = 1; i < (long long)a.size(); i++)
    pfxcnt[i] = pfxcnt[i - 1] + a[i].second,
    pfxsum[i] = pfxsum[i - 1] + a[i].first * a[i].second;
  sfxcnt[a.size() - 1] = a[a.size() - 1].second,
                    sfxsum[a.size() - 1] =
                        a[a.size() - 1].first * a[a.size() - 1].second;
  for (long long i = (long long)a.size() - 2; i >= 0; i--)
    sfxcnt[i] = sfxcnt[i + 1] + a[i].second,
    sfxsum[i] = sfxsum[i + 1] + a[i].first * a[i].second;
  for (long long i = 0; i < a.size(); i++) {
    long long val = a[i].first, freq = a[i].second;
    long long need = max(0ll, k - freq), curl = 0, curr = 0;
    if (need == 0) ans = 0;
    if (pfxcnt[i - 1] + sfxcnt[i + 1] < need || need == 0) continue;
    if (pfxcnt[i - 1] >= need) {
      curl = (val - 1) * pfxcnt[i - 1] - pfxsum[i - 1] + need;
    } else {
      curl = val * pfxcnt[i - 1] - pfxsum[i - 1] +
             (1e9 - val - 1) * sfxcnt[i + 1] -
             (1e9 * sfxcnt[i + 1] - sfxsum[i + 1]) + (need - pfxcnt[i - 1]);
    }
    if (sfxcnt[i + 1] >= need) {
      curr = ((1e9 - val - 1) * sfxcnt[i + 1]) - (1e9 * sfxcnt[i + 1]) +
             sfxsum[i + 1] + need;
    } else {
      curr = (1e9 - val) * sfxcnt[i + 1] -
             (1e9 * sfxcnt[i + 1] - sfxsum[i + 1]) + (val - 1) * pfxcnt[i - 1] -
             pfxsum[i - 1] + (need - sfxcnt[i + 1]);
    }
    ans = min({ans, curl, curr});
  }
  printf("%lld", ans);
}