配点 : $600$ 点

問題文

高橋君と青木君の家の庭には草 $1$, 草 $2$, $\ldots$, 草 $N$ の $N$ 本の草が生えており、草 $i$ の高さは $A_i$ です。 高橋君と青木君は次の方法で庭の草抜きを行う事にしました。

• まず、青木君が高々 $K$ 本の草を選んで抜く。
• その後、高橋君が次の操作を庭の草がすべて抜けるまで繰り返す。
  • 残っている草のうち高さが最大のものの高さを $H$ とする。残っている草のうち、高さが $\frac{H}{2}$ より高いものを一斉に抜く。

青木君は、高橋君の操作回数が最小となるようにした上で、自分の抜く本数を最小にしたいと考えています。 このときの高橋君の操作回数と青木君の抜く草の本数を求めてください。

制約

• $1 \leq N \leq 2\times 10^5$
• $0 \leq K \leq N$
• $1 \leq A_i \leq 10^9$
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$A_1$ $A_2$ $\ldots$ $A_N$

出力

高橋君の操作回数と青木君の抜く草の本数をこの順に空白区切りで出力せよ。

4 1
2 3 4 9

2 1

例えば青木君が草 $4$ (高さ $9$) を選んで抜いたとき、残りの草の中で最も高いものは草 $3$ であり、その高さは $4$ です。 $\frac{4}{2}=2$ であり、$2<3$, $2<4$ より $1$ 回目の操作で高橋君は草 $2$ と草 $3$ のみを抜くことができます。その後、 $2$ 回目の操作で草 $1$ を抜き、高橋君は $2$ 回で操作を終えることができます。 一方で、青木君がどの草を $1$ 本選んだとしても高橋君は $1$ 回で操作を終えることはできません。

また、もし青木君が $1$ 本も抜かなかったとすると高橋君は $3$ 回操作する必要があるため、青木君は高橋君の操作回数を最小にするために最低 $1$ 本は抜かなくてはなりません。

3 3
2 3 5

0 3

青木君が全ての草を抜いたとき高橋君は操作を行う必要がなく、明らかにこのときが最小です。

9 8
137 55 56 60 27 28 133 56 55

1 4