Algoritmizace B4B33ALG
Algoritmizace

Laboratory samples

Assignment

The samples have been collected from each site. There are some laboratories available which will analyze the samples. The number of samples collected on each site is equal to the number of these laboratories. The research manager has collected all the samples and he is going to make a package of samples for each laboratory. Each laboratory will receive one package and each package will contain one sample from each site. The sample material itself is quite valuable to the laboratories and it is desirable to distribute the samples among the laboratories as fairly as possible. The mass differences between particular packages should be minimal. The samples cannot be divided into smaller pieces.

img1sm
Image 1. Illustration to the Example 1 bellow. The groups on the image left side represent the sites, the groups on the right represent the laboratories with their respective packages. The distribution of the samples among the laboratories satisfies the conditions of the problem.

Task

You are given the masses of all samples. Find out how to distribute the samples into particular packages according to the given rules in such way that the difference between the mass of the heaviest and the mass of the lightest package is minimum possible.

Input

First line of input contains two positive integers N and L separated by space. N is the number of sites and L is the number of laboratories. Next, exactly N lines follow, each line represents one site. The line contains L positive integers separated by space, each integer represents mass of one sample from this site. The sites and the masses of the samples are not presented in any particular order. The value of N does not exceed 25, the value of L does not exceed 15. The mass of any sample does not exceed 300000.

Output

The output contains one text line with one integer equal to the minimum possible mass difference between the heaviest and the lightest package.

Examples

Example 1

Input
3 3
8 6 6
9 4 10
10 5 9
Output
3

The package masses will be 21 = 6 + 10 + 5, 22 = 8 + 4 + 10, 24 = 6 + 9 + 9.

Example 2

Input
4 4
3 6 4 4
6 3 7 2
2 5 5 3
8 8 6 8
Output
2

Example 3

Input
5 6
665 963 880 323 696 867
424 805 653 843 341 829
543 434 671 649 269 993
268 361 454 934 681 767
998 541 966 173 130 263
Output
4

Example 4

Input
6 5
289700 273481 222680 266660 248704
285552 296245 282755 237569 298152
289678 254817 233570 253502 262526
202363 276834 251284 299278 265538
281156 259030 247336 220085 292479
259055 231970 241460 201233 246462
Output
364

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.

Link to public data set