P10620 [ICPC 2013 WF] Low Power

你正在为机器制造先进的芯片。制造芯片很容易，但电源供应却成为了一个问题，因为现有电池的输出功率各不相同。 考虑 $n$ 台机器的问题，每台机器有两个芯片，每个芯片由 $k$ 块电池供电。出人意料的是，每个芯片获得的电量多少并不重要，但机器在两个芯片的功率输出尽可能接近时工作效果最佳。芯片的功率输出仅为其 $k$ 块电池中输出功率最小的那块电池的输出。 你有一堆共 $2nk$ 块电池，你需要将它们分配给这些芯片。可能无法分配这些电池使得每台机器的两个芯片的功率输出都相等，但你希望尽量减小它们之间的差异。具体来说，你希望告诉客户，所有机器中两个芯片的功率输出差异至多为 $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$ $(2nk \leq 10^6)$。第二行包含 $2nk$ 个整数 $p_i$，指定电池的功率输出 $(1 \leq p_i \leq 10^9)$。

输出一个最小的数字 $d$，使你可以分配这些电池，使每台机器中两个芯片的功率输出差异至多为 $d$。 翻译来自于：[ChatGPT](https://chatgpt.com/)。