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

Solution:
import sys

__author__ = 'ratmir'


def solveA(a, k):
    if k == 1:
        return 0
    levels = set()
    cnts = dict()
    for v in a:
        levels.add(v)
        if v in cnts:
            cnts[v] = cnts[v] + 1
            if cnts[v] >= k:
                return 0
        else:
            cnts[v] = 1
    levels = sorted(list(levels))
    if len(levels) == 1:
        return 0
    if len(levels) == 2:
        if cnts[levels[0]] > cnts[levels[1]]:
            return (levels[1] - levels[0]) * cnts[levels[1]] - (
                        cnts[levels[1]] - (k - max(cnts[levels[0]], cnts[levels[1]])))
        else:
            return (levels[1] - levels[0]) * cnts[levels[0]] - (
                        cnts[levels[0]] - (k - max(cnts[levels[0]], cnts[levels[1]])))

    ch_cnts = [cnts[levels[0]]]
    chs_cnts = [0]
    for i in range(1, len(levels)):
        ch_cnts.append((ch_cnts[i - 1] + cnts[levels[i]]))
        chs_cnts.append((chs_cnts[i - 1] + ch_cnts[i - 1] * (levels[i] - levels[i - 1])))
    chu_cnts = [0] * len(levels)
    chsu_cnts = [0] * len(levels)
    chu_cnts[len(levels) - 1] = cnts[levels[len(levels) - 1]]
    for ci in range(1, len(levels)):
        i = len(levels) - 1 - ci
        chu_cnts[i] = chu_cnts[i + 1] + cnts[levels[i]]
        chsu_cnts[i] = chsu_cnts[i + 1] + chu_cnts[i + 1] * (levels[i + 1] - levels[i])
    # print cnts
    # print ch_cnts
    # print chs_cnts
    # print chu_cnts
    # print chsu_cnts
    res = None
    #checking min
    sm = 0
    for cn in cnts:
        if cn!=levels[0]:
            levels_ = (cn -levels[0]-1) * cnts[cn]
            # cnts_levels_ = (k - cnts[levels[0]])
            sm += levels_
    sm += k -cnts[levels[0]]
    smu = 0
    for cn in cnts:
        if cn!=levels[len(levels)-1]:
            levels_ = (levels[len(levels)-1]-cn-1) * cnts[cn]
            # cnts_levels_ = (k - cnts[levels[0]])
            smu += levels_
    smu += k -cnts[levels[len(levels)-1]]
    res = min(sm,smu)

    for i in range(1, len(levels) - 1):
        cv = None
        # first from down
        count_d = ch_cnts[i]
        if k - count_d > 0:
            value_d = chs_cnts[i]
            full_shift = (k - count_d)
            remaining_shift = chu_cnts[i + 1] - full_shift
            value = value_d + chsu_cnts[i + 1] + full_shift * (levels[i + 1] - levels[i]) + remaining_shift * (
                        levels[i + 1] - levels[i] - 1)
            cv = value
        # print "first from up", i, value
        # first from down
        count_u = chu_cnts[i]
        if k - count_u > 0:
            value_u = chsu_cnts[i]
            full_shift = (k - count_u)
            remaining_shift = ch_cnts[i - 1] - full_shift
            value = value_u + chs_cnts[i - 1] + full_shift * (levels[i] - levels[i - 1]) + remaining_shift * (
                        levels[i] - levels[i - 1] - 1)
            if cv is None or value < cv:
                cv = value
        # print "first from down", i, value, cv
        # only from down
        if ch_cnts[i] >= k:
            full_shift = (k - cnts[levels[i]])
            remaining_shift = ch_cnts[i - 1] - full_shift
            value = chs_cnts[i - 1] + full_shift * (levels[i] - levels[i - 1]) + remaining_shift * (
                        levels[i] - levels[i - 1] - 1)
            if cv is None or value < cv:
                cv = value
            # print "from down", i, value
        # only from top
        if chu_cnts[i] >= k:
            full_shift = (k - cnts[levels[i]])
            remaining_shift = chu_cnts[i + 1] - full_shift
            value = chsu_cnts[i + 1] + full_shift * (levels[i + 1] - levels[i]) + remaining_shift * (
                        levels[i + 1] - levels[i] - 1)
            if cv is None or value < cv:
                cv = value
            # print "from up", i, value
        if cv is not None:
            if res is None or res > cv:
                res = cv
                # print i, res
        # print "Trying", i, levels[i]
        # print "From min", chs_cnts[i - 1]
        # print "From max", chsu_cnts[i + 1]
    return res


def solve():
    [n, k] = [int(x) for x in sys.stdin.readline().split()]
    a = [int(x1) for x1 in sys.stdin.readline().split()]
    return solveA(a, k)

print solve()