Nông dân John đang tổ chức một hội nghị ăn cỏ mới dành cho bò tại trang trại của mình!

Những cô bò từ khắp nơi trên thế giới đang đến sân bay địa phương để tham dự hội nghị và ăn cỏ. Cụ thể, có \(N\) cô bò đến sân bay (\(1 \leq N \leq 10^5\)), trong đó cô bò \(i\) đến vào thời điểm \(t_i\) (\(0 \leq t_i \leq 10^9\)). Nông dân John đã bố trí \(M\) chiếc xe buýt (\(1 \leq M \leq 10^5\)) để đưa các cô bò rời sân bay. Mỗi xe buýt có thể chở tối đa \(C\) cô bò (\(1 \leq C \leq N\)). Nông dân John đang chờ cùng các xe buýt tại sân bay và muốn phân các cô bò đến sân bay lên các xe. Một xe buýt có thể khởi hành vào thời điểm cô bò cuối cùng trên xe đến. Nông dân John muốn làm một người chủ nhà chu đáo nên không muốn để những cô bò mới đến phải chờ quá lâu tại sân bay. Nếu Nông dân John điều phối các xe buýt một cách tối ưu, giá trị nhỏ nhất có thể của thời gian chờ lớn nhất trong số mọi cô bò là bao nhiêu? Thời gian chờ của một cô bò là độ chênh lệch giữa thời điểm cô đến và thời điểm chiếc xe được phân cho cô khởi hành.

Đảm bảo rằng \(MC \geq N\).

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(C\) cách nhau bởi dấu cách. Dòng tiếp theo chứa \(N\) số nguyên cách nhau bởi dấu cách, biểu diễn thời điểm đến của mỗi cô bò.

Dữ liệu ra

In ra một dòng chứa giá trị nhỏ nhất có thể của thời gian chờ lớn nhất đối với bất kỳ cô bò nào.

Ví dụ

6 3 2
1 1 10 14 4 3

4

Nguồn

Đề bài gốc: USACO 2018 December Contest, Silver — Convention

Tác giả: Grace Cai