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

Solution:
import java.util.*;

/**
 * @ClassName EqualizingbByDivision
 * @Author mjlft
 * @Date 2019/9/1 17:23
 * @Version 1.0
 * @Description TODO
 */
public class EqualizingbByDivision {
    public static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        Node[] nums = new Node[2*100000 + 1];
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int max = 0;

        for(int i = 0; i < n; i ++){
            int index = scanner.nextInt();
            Node node = nums[index];
            if(node == null){
                node = new Node();
            }
            node.setNum(node.getNum() + 1);
            node.setSum(node.getNum());
            node.setIndex(index);
            nums[index] = node;
            if(max < index){
                max = index;
            }
        }

        for(int i = 0; i <= max; i ++){
            Node node = nums[i];
            if(node == null){
                node = new Node();
                nums[i] = node;
                continue;
            }

            if(node.getNum() >= k){
                System.out.println(0);
                return;
            }
            int index = i;
            int d = 1;
            while (true){
                index /= 2;
                Node child = nums[index];

//                child.setSum(child.getSum() + node.getNum());
                if(child.getSum() + node.getNum() >= k && !child.isOk()){
                    child.setTimes(child.getTimes() + d * (k - child.getSum()));
                    child.setSum(k);
                    child.setOk(true);
                }else {
                    if(!child.isOk()){
                        child.setTimes(child.getTimes() + d * node.getNum());
                        child.setSum(child.getSum() + node.getNum());
                    }
                }

                d ++;
                if(index == 0){
                    break;
                }
            }
        }

        int min = Integer.MAX_VALUE;
        for(Node node : nums){
            if(node != null && node.isOk() && node.getTimes() < min){
                min = node.getTimes();
            }
        }
        System.out.println(min);
    }
}
class Node{
    private int num;
    private int times;
    private boolean ok = false;
    private int sum;
    private int index;

    public int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }

    public int getTimes() {
        return times;
    }

    public void setTimes(int times) {
        this.times = times;
    }

    public boolean isOk() {
        return ok;
    }

    public void setOk(boolean ok) {
        this.ok = ok;
    }


    public int getSum() {
        return sum;
    }

    public void setSum(int sum) {
        this.sum = sum;
    }

    public int getIndex() {
        return index;
    }

    public void setIndex(int index) {
        this.index = index;
    }

    @Override
    public String toString() {
        return "Node{" +
                "num=" + num +
                ", times=" + times +
                ", ok=" + ok +
                ", sum=" + sum +
                ", index=" + index +
                '}';
    }
}