Low Power

You are designing advanced chips for machines. Manufacturing the chips is straightforward, but supplying power to them is challenging because the available batteries have varied output powers.

Consider the situation where there are $n$ machines, each with two chips. Each chip requires $k$ batteries for power. Surprisingly, it does not matter how much total power each chip receives, but a machine works best when its two chips have output powers as close as possible. The output power of a chip is the minimum output power among its $k$ batteries.

You have $2nk$ batteries in total, and you must assign them to the chips. It may be impossible to allocate the batteries so that in every machine the two chips have equal output powers. However, you want to allocate the batteries so that, in all machines, the difference between the output powers of the two chips is minimized. Specifically, you want to guarantee to your customers that, in every machine, the difference between the output powers of its two chips does not exceed $d$, and you want to make $d$ as small as possible. To do this, you must determine an optimal allocation of the batteries to the machines.

Consider Sample Input 1. There are $2$ machines, each requiring $3$ batteries per chip, and a supply of batteries with output powers $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$, $10$, $11$, $12$. For example, you can assign the batteries with output $1$, $3$, $5$ to one chip and $2$, $4$, $12$ to the other chip of the same machine; and assign $6$, $8$, $9$ to the third chip, and $7$, $10$, $11$ to the fourth chip. The chip output powers are $1$, $2$, $6$, and $7$ respectively, and in both machines the difference between the chips' output powers is $1$. Note that there are other ways to achieve the same result.