The original order does not matter in this problem, so we can safely sort the heights in the ascending order. Then we can calculate for each height the range it can cover if it is the highest at the moment of an operation, and we will have an increasing array of segments.

For example, the heights \([2, 3, 4, 9]\) will become segments \([[1, 1], [1, 2], [2, 3], [4, 4]]\).

Our goal is to choose several non-overlapping segments such that the remaining positions do not exceed \(K\). And we need to first minimize the number of chosen segments and then minimize the number of remaining positions.

An observation is that in this problem, the segments are not arbitrary. Consider the situation in which Aoki removes no weeds at first. Then Takahashi would need to operate at most \(\log\operatorname{\max A_i} + 1\) times, since in each operation, the maximum height of the remaining weeds is at least cut by half.

So we will need no more than \(\log\operatorname{\max A_i} + 1\) operations.

Now we can use dynamic programming to solve this problem. Let \(dp[i][j]\) mean the minimum number of remaining weeds (that is to say, Aoki needs to pull these weeds at first) if we cover the range \([1,i]\) with \(j\) operations. There are two types of transitions:

1. We perform an operation with the \(i\)-th weed as the highest, thus transit from \((l[i]-1,j-1)\) to \((i,j)\).
2. We skip the \(i\)-th weed (let Aoki pull it), thus transit from \((i-1,j)\) to \((i,j)\).

• Time complexity is \(\mathcal{O}(N\log\operatorname{HMAX})\), where \(\operatorname{HMAX}=10^9\).
• Space complexity is \(\mathcal{O}(N\log\operatorname{HMAX})\).

use proconio::input;

const K: usize = 31;

fn main() {
    input! {
        n: usize,
        k: usize,
        mut a: [usize; n],
    }

    if k == n {
        println!("0 {}", n);
        std::process::exit(0);
    }

    a.sort();
    let mut l = vec![0; n];
    for i in 0..n {
        let mut lo = 0;
        let mut hi = i;
        while lo <= hi {
            let mid = (lo + hi) >> 1;
            if a[mid] > a[i] / 2 {
                if mid == 0 {
                    break;
                }
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        l[i] = lo;
    }

    let mut dp = vec![vec![k + 1; K]; n + 1];
    dp[0][0] = 0;
    for i in 0..n {
        for j in 0..K {
            if j + 1 < K {
                dp[i + 1][j + 1] = dp[i + 1][j + 1].min(dp[l[i]][j]);
            }
            dp[i + 1][j] = dp[i + 1][j].min(dp[i][j] + 1);
        }
    }

    for i in 1..K {
        if dp[n][i] <= k {
            println!("{} {}", i, dp[n][i]);
            std::process::exit(0);
        }
    }
}