저전력

기계에 들어갈 고성능 칩을 만들고 있습니다. 칩 자체를 만드는 것은 쉽지만, 사용할 수 있는 배터리마다 출력이 제각각이라 전원 공급이 까다롭습니다.

기계가 $n$대 있습니다. 각 기계에는 칩이 두 개 있고, 각 칩은 정확히 $k$개의 배터리로 전원을 공급받습니다. 칩이 받는 절대적인 전력량 자체는 중요하지 않습니다. 한 기계는 두 칩의 출력이 서로 최대한 비슷할 때 가장 잘 작동합니다. 칩의 출력은 그 칩에 들어간 $k$개 배터리의 출력 중 가장 작은 값으로 정의됩니다.

배터리 $2nk$개를 모두 칩에 나누어 배분해야 합니다(모든 배터리를 사용하고, 각 칩은 정확히 $k$개씩 받습니다). 모든 기계에서 두 칩의 출력을 똑같이 맞추는 것은 불가능할 수 있으므로, 대신 모든 기계에서 두 칩의 출력 차이가 최대 $d$ 이하가 되도록 보장하고, 그 $d$를 가능한 한 작게 만들고 싶습니다. 이때 가능한 가장 작은 $d$를 구하세요.

예를 들어 기계가 $2$대이고 칩마다 배터리가 $3$개이며 배터리 출력이 $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12$라고 합시다. 한 가지 방법으로 출력 $1, 3, 5$를 한 칩에, 같은 기계의 다른 칩에 $2, 4, 12$를, 세 번째 칩에 $6, 8, 9$를, 네 번째 칩에 $7, 10, 11$을 배분할 수 있습니다. 그러면 네 칩의 출력은 각각 $1, 2, 6, 7$이 되어 두 기계 모두 차이가 $1$입니다. 같은 결과를 내는 배분 방법은 이 밖에도 많습니다.

입력은 하나의 테스트 케이스로 이루어집니다. 첫째 줄에는 양의 정수 두 개, 기계의 수 $n$과 칩당 배터리 수 $k$가 주어집니다($2nk \le 10^6$). 둘째 줄에는 배터리들의 출력을 나타내는 정수 $2nk$개 $p_i$가 주어집니다($1 \le p_i \le 10^9$).

모든 기계에서 두 칩의 출력 차이가 최대 $d$ 이하가 되도록 배터리를 배분할 수 있는 가장 작은 수 $d$를 출력하세요.