Laboratory samples
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.
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. |
The 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.
Example 1
Input3 3 8 6 6 9 4 10 10 5 9Output
3The package masses will be 21 = 6 + 10 + 5, 22 = 8 + 4 + 10, 24 = 6 + 9 + 9.
Example 2
Input4 4 3 6 4 4 6 3 7 2 2 5 5 3 8 8 6 8Output
2
Example 3
Input5 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 263Output
4
Example 4
Input6 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 246462Output
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