D - 花束の仕分け 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は花屋でアルバイトをしています。今日は N 本の花を K 個の花束に仕分ける作業を任されました。

各花 i（1 \leq i \leq N）には「茎の長さ」を表す整数 A_i が定められています。N 本の花すべてを K 個の花束のいずれかちょうど 1 つに割り当てます。ただし、各花束に入れられる花の本数は 0 本以上 M 本以下です。花が 1 本も入っていない花束があっても構いません。

同じ花束に入れる花どうしで茎の長さの差が大きいと、見栄えが悪くなってしまいます。そこで高橋君は、非負整数 D を用いた次の条件を満たすように花を仕分けたいと考えています。

  • 花が 2 本以上入っているどの花束についても、その花束に含まれる花の茎の長さの最大値と最小値の差が D 以下である。

花が 0 本または 1 本のみの花束については、この条件は自動的に満たされます。

D が小さいほど各花束の見栄えは良くなりますが、D を小さくしすぎると K 個の花束ではすべての花を仕分けられなくなることがあります。一方、D を十分大きくすれば、各花束の容量制約 M 本以下のみを考えればよくなり、K \times M \geq N が保証されているため、必ず仕分けることができます。

すべての N 本の花を上記の条件を満たすように K 個の花束に割り当てることが可能となる D の最小値を求めてください。A_i はすべて整数であるため、答えも非負整数となります。

制約

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

入力

N K M
A_1 A_2 \ldots A_N
  • 1 行目には、花の本数を表す整数 N、花束の個数を表す整数 K、各花束に入れられる花の最大本数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各花の茎の長さを表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

すべての N 本の花を条件を満たすように割り当てられる D の最小値を 1 行で出力せよ。

入力例 1

5 2 3
1 3 5 8 10

出力例 1

4

入力例 2

4 2 2
1 5 10 20

出力例 2

10

入力例 3

10 3 4
2 5 8 11 15 20 25 30 33 37

出力例 3

10

入力例 4

20 5 5
3 7 12 18 25 31 38 42 50 55 63 70 78 85 90 96 100 108 115 120

出力例 4

20

入力例 5

1 1 1
1000000000

出力例 5

0

Score : 400 pts

Problem Statement

Takahashi works part-time at a flower shop. Today he has been assigned the task of sorting N flowers into K bouquets.

Each flower i (1 \leq i \leq N) has an integer A_i representing its "stem length." All N flowers must be assigned to exactly one of the K bouquets. However, the number of flowers in each bouquet must be between 0 and M, inclusive. It is acceptable for a bouquet to contain no flowers at all.

If flowers in the same bouquet have a large difference in stem length, the bouquet will look unappealing. Therefore, Takahashi wants to sort the flowers so that the following condition is satisfied using a non-negative integer D:

  • For every bouquet containing 2 or more flowers, the difference between the maximum and minimum stem lengths of the flowers in that bouquet is at most D.

For bouquets containing 0 or 1 flowers, this condition is automatically satisfied.

The smaller D is, the better each bouquet looks, but if D is too small, it may become impossible to sort all the flowers into K bouquets. On the other hand, if D is sufficiently large, only the capacity constraint of at most M flowers per bouquet needs to be considered, and since K \times M \geq N is guaranteed, it is always possible to sort the flowers.

Find the minimum value of D such that it is possible to assign all N flowers to K bouquets while satisfying the above condition. Since all A_i are integers, the answer is also a non-negative integer.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq M \leq N
  • K \times M \geq N
  • 1 \leq A_i \leq 10^9
  • All input values are integers.

Input

N K M
A_1 A_2 \ldots A_N
  • The first line contains three space-separated integers: N representing the number of flowers, K representing the number of bouquets, and M representing the maximum number of flowers per bouquet.
  • The second line contains space-separated integers A_1, A_2, \ldots, A_N representing the stem length of each flower.

Output

Print in one line the minimum value of D such that all N flowers can be assigned while satisfying the condition.

Sample Input 1

5 2 3
1 3 5 8 10

Sample Output 1

4

Sample Input 2

4 2 2
1 5 10 20

Sample Output 2

10

Sample Input 3

10 3 4
2 5 8 11 15 20 25 30 33 37

Sample Output 3

10

Sample Input 4

20 5 5
3 7 12 18 25 31 38 42 50 55 63 70 78 85 90 96 100 108 115 120

Sample Output 4

20

Sample Input 5

1 1 1
1000000000

Sample Output 5

0