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 operator
import sys
from collections import Counter
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_counter = Counter()
    for e in keys:
        v = e
        while v > 0:
            base_number_counter[v] += number_counter[e]
            v //= 2
    values = sorted(filter(lambda x: x[1] >= k, base_number_counter.items()), key=operator.itemgetter(1, 0))

    res = float('inf')
    for value, count in values:
        c = 0
        op_count = 0

        for e in keys:
            if c >= k:
                break
            v = e
            shifts = 0
            while v > value:
                v //= 2
                shifts += 1
            if v == value:
                raise_count = min(k - c, number_counter[e])
                c += raise_count
                op_count += (raise_count * shifts)

        if c >= 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)