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

Solution:
import math
import sys
from collections import Counter
from collections import defaultdict
from typing import List

input = sys.stdin.readline


def get_degree(n: int):
    return int(math.floor(math.log2(n)))


def solve(n: int, k: int, a: List[int]) -> int:
    number_counter = Counter(a)
    # a = sorted(a)
    keys = sorted(number_counter.keys())

    base_number_dict = defaultdict(list)
    for e in keys:
        v = e
        shifts = 0
        while v > 0:
            base_number_dict[v].extend([shifts] * number_counter[e])
            shifts += 1
            v //= 2

    res = float('inf')
    for key in base_number_dict.keys():
        elems = sorted(base_number_dict[key])
        if len(elems) < k:
            continue
        op_count = sum(elems[:k])
        res = min(res, op_count)

    return res


# assert solve(50, 7,
#              [199961, 199990, 199995, 199997, 199963, 199995, 199985, 199994, 199974, 199974, 199997, 199991, 199993,
#               199982, 199991, 199982, 199963, 200000, 199994, 199997, 199963, 199991, 199947, 199996, 199994, 199995,
#               199995, 199990, 199972, 199973, 199980, 199955, 199984, 199998, 199998, 199992, 199986, 199986, 199997,
#               199995, 199987, 199958, 199982, 199998, 199996, 199995, 199979, 199943, 199992, 199993]) == 7
# assert solve(50, 2, [72548, 51391, 1788, 171949, 148789, 151619, 19225, 8774, 52484, 74830, 20086, 51129, 151145, 87650,
#                      108005, 112019, 126739, 124087, 158096, 59027, 34500, 87415, 115058, 194160, 171792, 136832, 1114,
#                      112592, 171746, 199013, 101484, 182930, 185656, 154861, 191455, 165701, 140450, 3475, 160191,
#                      122350, 66759, 93252, 60972, 124615, 119327, 108068, 149786, 8698, 63546, 187913]) == 12
# assert solve(5, 3, [1, 2, 2, 4, 5]) == 1

n, k = map(int, input().split())
a = list(map(int, input().split()))

res = solve(n, k, a)
print(res)