Orchestras

In an orchestra, there are K different musical instruments. For each of these musical instruments, we have N musicians available, so a total of K~\mathbf{\times}~N musicians. We can thus form N different orchestras.

To participate in an orchestra, a musician must receive a monetary amount as compensation, and for each musician, we know the amount. Some musicians are "more expensive," meaning they ask for a larger compensation amount, while others are "cheaper," meaning they ask for a smaller compensation amount.

We define the "deviation" of an orchestra as the difference between the compensation amount received by the most expensive musician participating in it and the compensation amount received by the cheapest musician participating in it. We want to place the musicians in the N orchestras in such a way that the largest deviation D appearing in one or more of the formed orchestras is as small as possible.

Problem:

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that reads the values of N and K, as well as the compensation amounts requested by the musicians, and prints the minimum possible value of D.

Input File:

The input file named orchestras.in is a text file with the following structure. The first line contains two integers N and K, separated by a space: the number of orchestras and the number of instruments. Following are K lines, one for each musical instrument. Each of these lines contains N positive integers, separated in pairs by a space: the desired compensation of each musician playing the respective musical instrument.

Output File:

The output file named orchestras.out is a text file containing a single line with an integer: the minimum possible value of D.

Examples of Input - Output Files:

1ο

STDIN (orchestras.in)

5 2
20 12 5 18 11
8 19 16 7 17

STDOUT (orchestras.out)

4

Explanation: We have 2 musical instruments, and each of them is played by 5 musicians. We can create 5 orchestras as follows:

• In the 1^st orchestra, we place the musicians with compensations 18 and 19 (deviation 1).
• In the 2^nd orchestra, we place the musicians with compensations 12 and 16 (deviation 4).
• In the 3^rd orchestra, we place the musicians with compensations 7 and 11 (deviation 4).
• In the 4^th orchestra, we place the musicians with compensations 5 and 8 (deviation 3).
• In the 5^th orchestra, we place the musicians with compensations 20 and 17 (deviation 3). The maximum deviation D achieved in this way is 4. There is no way to form the 5 orchestras to achieve a smaller value of D.

2ο

STDIN (orchestras.in)

4 2
17 42 7 23
42 23 17 7

STDOUT (orchestras.out)

0

Explanation: We can form 4 orchestras in which both musicians receive the same compensation.

3ο

STDIN (orchestras.in)

2 3
25 48
27 16
7 15

STDOUT (orchestras.out)

33

Constraints:

• 1 ~\le~ N ~\le~ 5.000
• 2 ~\le~ K ~\le~ 200
• The desired compensation for each musician will not exceed 10⁶.
• For test cases with a total value of 50%, K = 2.
• For test cases with a total value of 50%, 1 ~\le~ N ~\le~ 10.

Attention! Be sure to read the input and print the output efficiently, especially if you are programming in C++ or Java. Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 256 MB.