레이팅 미적용당신은 기계에 들어갈 첨단 칩을 만들고 있다. 칩을 만드는 것은 쉽지만, 공급 가능한 배터리들의 출력이 제각각이라 전원 공급이 문제가 된다. 각각 칩 두 개를 갖는 기계 \(n\)대가 있고, 각 칩은 배터리 \(k\)개로 구동되는 상황을 생각하자. 놀랍게도 각 칩이 얼마나 많은 전력을 받는지는 중요하지 않지만, 기계는 두 칩의 전력 출력이 최대한 비슷할 때 가장 잘 작동한다. 칩의 전력 출력은 단순히 그 칩의 \(k\)개 배터리 중 가장 작은 전력 출력이다. 칩들에 배정할 배터리 2\(nk\)개의 재고가 있다. 모든 기계에서 두 칩의 전력 출력이 같도록 배터리를 배정하는 것은 불가능할 수도 있지만, 차이가 가능한 한 작도록 배정하고 싶다. 정확히 말하면, 모든 기계에서 두 칩의 전력 출력 차이가 최대 \(d\)라고 고객에게 말할 수 있도록 하고, \(d\)를 가능한 한 작게 만들고 싶다. 이를 위해 배터리를 기계들에 최적으로 배정하는 방법을 결정해야 한다. 샘플 입력 1을 보자. 기계가 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\) (2\(nk \le 10^{6}\))가 주어진다. 둘째 줄에는 배터리들의 전력 출력을 나타내는 2\(nk\)개의 정수 \(pi\) (\(1 \le pi \le 10^{9}\))가 주어진다.
각 기계에서 두 칩의 전력 출력 차이가 최대 \(d\)가 되도록 배터리를 배정할 수 있는 가장 작은 수 \(d\)를 출력한다.
2 3
1 2 3 4 5 6 7 8 9 10 11 12
1
2 2
3 1 3 3 3 3 3 3
2