penguin's compare heights (Easy)

2 secs 1024 MB
penguin8331's icon penguin8331

問題文

NN匹のペンギンがいます。
各ペンギンの身長はそれぞれA1,A2,...,ANA_1,A_2,...,A_Nです。
いまTysonくんはこのすべてのペンギンをMM個の水槽に分けようとしています。
しかしこの水槽は1つにつきKK匹までしかペンギンを入れることができません(0匹でもよい)。
また全てのペンギンはそのペンギンが入っている水槽で最も身長の高いペンギンとの身長の差だけ不幸さを感じます。各ペンギンの不幸さの最大値をもっとも小さくするとき、最小の値を答えよ。
しかしすべてのペンギンを水槽に入れることができなければ -1 を出力せよ

制約

  • 1N,M,K1051 \leq N,M,K \leq 10^5
  • 1Ai1091 \leq A_i \leq 10^9
  • 入力される値は全て整数

入力

NN MM KK
A0A_0 A1A_1 ...... ANA_N

出力

計算結果を一行に出力せよ。
しかし水槽にすべてのペンギンが入らない場合は -1 を出力せよ

サンプル

入力例1
5 2 4
9 6 3 5 10 
出力例1
3

身長が 6,3,5 のペンギンと 9,10 のペンギンで 2 つの水槽に分けるのが最適です


入力例2
5 2 100
6 3 5 7 1000000
出力例2
4

身長が 9,6,3,5,7 のペンギンと 1000000 のペンギンで 2 つの水槽に分けるのが最適です


入力例3
5 2 2
9 6 3 5 10 
出力例3
-1

水槽が 2 個しかなくそれぞれの水槽には 2 匹までしか入れることができないため、最大でも水槽には 4 匹しか入れることができず 5 匹入れることはできません

Submit


Go (1.21)