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:
rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())

from collections import Counter
def solve(N, K, A):
    count = Counter(A)
    B = []
    for k in sorted(count):
        B.append([k, count[k]])
    ans = sum(A)

    prefix = [[0,0] for _ in B]
    suffix = [[0,0] for _ in B]

    #prefix[i]: how many people and what cost to get
    #          them to B[i][0]
    for i in xrange(len(B)):
        k, c = B[i]
        prefix[i][0] = prefix[i-1][0] + c
        cost = 0 if i==0 else B[i][0] - B[i-1][0]
        prefix[i][1] = prefix[i-1][1] + prefix[i-1][0] * cost

    for i in xrange(len(B) - 1, -1, -1):
        k, c = B[i]
        suffix[i][0] += c
        if i+1<len(B): suffix[i][0] += suffix[i+1][0]
        cost = 0 if i==len(B)-1 else B[i+1][0] - B[i][0]
        if i+1<len(B):
            suffix[i][1] += suffix[i+1][0] * cost
            suffix[i][1] += suffix[i+1][1]
            
    #print prefix
    #print suffix
    #print "B", B
    for i, (k, c) in enumerate(B):
        if c >= K:
            return 0
        slack = K - c
        #print "SLACK", slack
        leftppl=leftcost=rightppl=rightcost=0
        if i - 1 >= 0:
            leftppl = prefix[i-1][0]
            leftcost = prefix[i-1][1]
        if i + 1 < len(B):
            rightppl = suffix[i+1][0]
            rightcost = suffix[i+1][1]
            
        # want slack more people
        if leftppl >= slack:
            # can draft just from left
            cand = prefix[i][1] - (leftppl - slack)
            #print("L", cand, i, k, c, ';', slack, leftppl, leftcost)
            if cand < ans: ans = cand
        if rightppl >= slack:
            # just from right
            cand = suffix[i][1] - (rightppl - slack)
            #print("R", cand, 'on', suffix[i][1], rightppl,slack)
            if cand < ans: ans = cand

        # Try to draft both
        if 0 < i < len(B) - 1:
            # first way: prioritize left
            cand = prefix[i][1]
            slackrem = slack - leftppl
            cand += suffix[i][1] - (rightppl - slackrem)
            if cand < ans: ans = cand

            # second way
            cand = suffix[i][1]
            slackrem = slack - rightppl
            cand += prefix[i][1] - (leftppl - slackrem)
            if cand < ans: ans = cand

    return ans

N, K = rrm()
print solve(N, K, rrm())