配点 : $500$ 点

問題文

丸太が $N$ 本あり、それぞれ長さは $A_1,A_2,\cdots,A_N$ です。

これらの丸太を合計 $K$ 回まで切ることができます。 長さ $L$ の丸太を片端から $t (0 の位置で切ると、長さ$t,L-t$ の丸太に分かれます。

丸太を合計 $K$ 回まで切った後最も長い丸太の長さが最小でいくつになるか求め、小数点以下を切り上げた値を出力してください。

制約

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

入力

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

$N$ $K$

$A_1$ $A_2$ $\cdots$ $A_N$

出力

答えとなる整数を出力せよ。

2 3
7 9

4

• まず、長さ $7$ の丸太を片端から $3.5$ の位置で切り、長さ $3.5$ の丸太二本に分けます。
• 次に、長さ $9$ の丸太を片端から $3$ の位置で切り、長さ $3$ と $6$ の丸太に分けます。
• 最後に、長さ $6$ の丸太を片端から $3.3$ の位置で切り、長さ $3.3$ と $2.7$ の丸太に分けます。

すると、最も長い丸太の長さは $3.5$ になります。これが最小なので、小数点以下を切り上げた $4$ を出力します。

3 0
3 4 5

5

10 10
158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202

292638192