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:
#!/usr/bin/env python3
import unittest
import traceback
import pprint


def compress_list(a):
    x = []
    cur = a[0]
    num = 1
    for i in range(1, len(a)):
        if a[i] == cur:
            num += 1
        else:
            x.append([cur, num])
            cur = a[i]
            num = 1
    x.append([cur, num])
    return x


def solve(n, k, a):
    a = sorted(a)
    a = compress_list(a)
    min_ret = 200000000
    x = {0: [0 for i in range(0, 20)]}
    for cur, num in a:
        if num >= k:
            return 0
        idx = 0
        while cur > 0:
            if cur not in x:
                x[cur] = [0 for i in range(0, 20)]
            x[cur][idx] += num
            cur = cur // 2
            idx += 1
    for cur, ll in x.items():
        snum = 0
        scnt = 0
        for idx, num in enumerate(ll):
            if snum + num >= k:
                ret = scnt + (k -  snum) * idx
                min_ret = min(min_ret, ret)
                break
            snum += num
            scnt += num * idx
            if scnt >= min_ret:
                break
    # pprint.pprint(a)
    # pprint.pprint(x)
    return min_ret


class TestCase(unittest.TestCase):
    def test1(self):
        n = 5
        k = 3
        a = [2, 2, 3, 3, 5]
        self.assertEqual(solve(n, k, a), 1)

    def test2(self):
        n = 5
        k = 3
        a = [1, 2, 2, 4, 5]
        self.assertEqual(solve(n, k, a), 1)

    def test3(self):
        n = 5
        k = 3
        a = [1, 2, 3, 4, 5]
        self.assertEqual(solve(n, k, a), 2)

    def test4(self):
        n = 5
        k = 3
        a = [1, 2, 3, 3, 3]
        self.assertEqual(solve(n, k, a), 0)

    def test5(self):
        n = 10
        k = 4
        a = [4, 4, 8, 17, 25, 30, 99, 68, 89, 200]
        self.assertEqual(solve(n, k, a), 3)

    def test6(self):
        n = 1
        k = 1
        a = [1337]
        self.assertEqual(solve(n, k, a), 0)

if __name__ == "__main__":
    n, k = [int(i) for i in input().split()]
    a = [int(i) for i in input().split()]
    try:
        print(solve(n, k, a))
    except Exception as e:
        print(e, traceback.format_exc())