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
# import numpy as np

def get_num_operations(m, x):
    if x < m: return big_number
    if x == m: return 0
    return 1 + get_num_operations(m, int(x / 2))


big_number = 10000000

n, k=map(int, input().split())
elements_array = list(map(int, input().split()))

answer_elements = set()
answer_elements.add(0)
for element in elements_array:
    while element > 0:
        answer_elements.add(element)
        element = int(element / 2)


max_element = int(max(elements_array))
best_result = big_number
for m in answer_elements:
    cur_results_array = list()
    k_elements = 0
    for element in elements_array:
        cur_operations = get_num_operations(m, element)
        # if cur_operations < big_number:
        #     k_elements += 1
        cur_results_array.append(cur_operations)
        # if k_elements == k:
        #     break
    
    cur_results_array.sort()
    cur_operations = sum(cur_results_array[:k])
    best_result = min(best_result, cur_operations)

print(best_result)