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:
from __future__ import division, print_function
_interactive = False

def discrete_ternary_search(func, lo, hi):
    """ Find the first maximum of unimodal function func() within [lo, hi] """
    while lo <= hi:
        lo_third = lo + (hi - lo) // 3
        hi_third = lo + (hi - lo) // 3 + (1 if 0 < hi - lo < 3 else (hi - lo) // 3)

        if func(lo_third) > func(hi_third):
            lo = lo_third + 1
        else:
            hi = hi_third - 1

    return lo


def main():
    n, k = input_as_list()
    ar = input_as_list()
    ar.sort()

    from collections import Counter
    ctr = Counter(ar)
    if k <= max(ctr.itervalues()):
        print(0)
        return
    
    def f(x):
        ans = 0
        for e in ar:
            ans += abs(x-e)
        return max(0, ans-n+k)

    v = discrete_ternary_search(f, 0, 10**9+1)

    ans = f(v)
    k -= 1
    s = 0
    for i in range(k):
        s += ar[k] - ar[i]
    s = max(s-ar[k+1:].count(ar[k]), 0)
    ans = min(ans, s)

    s = 0
    ar2 = ar[::-1]
    for i in range(k):
        s += ar2[i] - ar2[k]
    s = max(s-ar2[k+1:].count(ar2[k]), 0)
    ans = min(ans, s)

    print(ans)


# Constants
INF = float('inf')
MOD = 10**9+7
alphabets = 'abcdefghijklmnopqrstuvwxyz'

# Python3 equivalent names
import os, sys, itertools
if sys.version_info[0] < 3:
    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip

# print-flush in interactive problems
if _interactive:
    flush = sys.stdout.flush()
    def printf(*args, **kwargs):
        print(*args, **kwargs)
        flush()

# Debug print, only works on local machine
LOCAL = "LOCAL_" in os.environ
debug_print = (print) if LOCAL else (lambda *x, **y: None)

# Fast IO
if (not LOCAL) and (not _interactive):
    from io import BytesIO
    from atexit import register
    sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
    sys.stdout = BytesIO()
    register(lambda: os.write(1, sys.stdout.getvalue()))
    input = lambda: sys.stdin.readline().rstrip('\r\n')

# Some utility functions(Input, N-dimensional lists, ...)
def input_as_list():
    return [int(x) for x in input().split()]

def input_with_offset(o):
    return [int(x)+o for x in input().split()]

def input_as_matrix(n, m):
    return [input_as_list() for _ in range(n)]

def array_of(f, *dim):
    return [array_of(f, *dim[1:]) for _ in range(dim[0])] if dim else f()

main()