index.md

討伐天蠍座

\begin{figure}[h] \centering \includegraphics[width=12cm]{img.jpg} \caption{里見蓮太郎與其搭檔藍原延珠一起扣動天梯的板機將天蠍座擊敗，出自動畫《黑色子彈》} \end{figure}

西元2021年，人類在與病毒性寄生生物「原腸動物」的戰爭中敗北，被驅逐至狹窄的領土，帶著恐懼與絕望苟且偷生。至此過了十年，人類在能控制原腸動物病毒的少女們「受詛之子」力量下得以找到對抗怪物的最後希望。

每個「受阻之子」會擔任「起始者」，並和一位「促進者」組成戰鬥人員搭檔去討伐原腸動物。而根據起始者與促進者搭擋所打倒原腸動物數量和戰果，國際起始者監督機構 IISO 會給予他們 IP 排名以代表他們的實力。

近期，他們即將討伐階段V的原腸動物－天蠍座。為此，他們需要將 $n$ 組戰鬥人員分配成 $k$ 隊以從各個方向擊破這個的可怕原腸動物。

然而如果組別內人員的實力差距過大，就很有可能出現實力較差的搭檔扯實力較強的搭檔的後腿，導致戰鬥人員無法發揮全部的實力。為了避免這種情況，請你幫他們找出一種分隊方式，使得這 $k$ 隊中最大的全距盡可能的小。

（每組的搭檔數沒有上限或下限，意即可以有一組有 $n$ 組搭檔或有一組沒有任何搭檔。）

\clearpage

輸入

輸入第一行有兩個正整數 $n,~k$。
輸入第二行有 $n$ 個正整數 $p_1,p_2,...,~p_n$ ，代表每個戰鬥人員搭檔的 IP 排名。

輸出

輸出一行，包含一個整數，代表 $k$ 隊中最大全距的最小可能。

輸入限制

• $1 \leq k \leq n \leq 10^6$
• $1 \leq p_i \leq 10^9$

子任務

\subtasks

\clearpage

範例輸入

\testfile{0-01.in}

範例輸出

\testfile{0-01.out}

範例說明

分為 {1, 5} 和 {7, 8, 9, 10}，兩隊的全距分別為 $5 - 1 = 4$ 和 $10 - 7 = 3$，最大的全距為 4。

提示

一組資料的全距為資料中的最大值減最小值。