Low Power

Time limit4sMemory limit256 MB

Summary

Sort 2nk batteries into groups of k and pair the group minima into n machines to minimize the largest pair gap.

Level: Medium6 of 10
Topics: Binary search, Greedy, Sorting
Solved: No attempts yet

Problem

You are building advanced chips for machines. The chips themselves are easy to make, but powering them is tricky because the available batteries have widely varying power outputs.

There are $n$ machines. Each machine has two chips, and each chip is powered by exactly $k$ batteries. The absolute amount of power a chip receives does not matter; a machine works best when its two chips have power outputs that are as close as possible. The power output of a chip is defined as the smallest power output among its $k$ batteries.

You must distribute all $2nk$ batteries among the chips (every battery is used, and each chip receives exactly $k$ of them). It may be impossible to make both chips of every machine have equal power output, so instead you want to guarantee that in every machine the two chips' power outputs differ by at most $d$ , and you want $d$ to be as small as possible. Find that smallest possible $d$ .

For example, suppose there are $2$ machines with $3$ batteries per chip and batteries with power outputs $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12$ . One valid distribution assigns powers $1, 3, 5$ to one chip, $2, 4, 12$ to the other chip of the same machine, $6, 8, 9$ to the third chip, and $7, 10, 11$ to the fourth. The four chip power outputs are then $1, 2, 6, 7$ , so both machines have a difference of $1$ . Many other distributions achieve the same result.

Input

The input is a single test case. The first line contains two positive integers: the number of machines $n$ and the number of batteries per chip $k$ (with $2nk \le 10^6$ ). The second line contains $2nk$ integers $p_i$ , the power outputs of the batteries (with $1 \le p_i \le 10^9$ ).

Output

Print the smallest number $d$ such that the batteries can be distributed so that, in every machine, the two chips' power outputs differ by at most $d$ .

Examples6

Example 1
Input
```
2 3
1 2 3 4 5 6 7 8 9 10 11 12
```
Expected output
```
1
```
Example 2
Input
```
1 1
8 5
```
Expected output
```
3
```
Example 3
Input
```
1 2
11 1 2 10
```
Expected output
```
1
```
Example 4
Input
```
3 1
20 1 9 6 10 5
```
Expected output
```
10
```
Example 5
Input
```
2 2
4 4 4 4 4 4 4 4
```
Expected output
```
0
```
Example 6
Input
```
2 1
100 11 10 1
```
Expected output
```
89
```