KOIREP  Representatives
There are N classes in a school, each with M students. There is going to be a race of 100m dash, and a representative from each class will be chosen to participate in this race. You were assigned a task to choose these representatives. Since you did not want the race to be one sided, you wanted to choose the representatives such that the difference between the ability of the best representative and the worst representative is minimal.
For example, if N = 3 and M = 4, and each class has students with following abilities:
Class 1: {12, 16, 67, 43}
Class 2: {7, 17, 68, 48}
Class 3: {14, 15, 77, 54}
it is best to choose the student with ability 16 from Class 1, 17 from Class 2, and 15 from Class 3. Thus, the difference in this case would be 1715 = 2.
Your task is to calculate the minimal possible difference you can achieve by choosing a representative from each class.
Input
The first line of the input consists of two integers, N and M. (1<=N<=1000, 1<=M<=1000).
The next N lines will have M integers. The jth element of ith line is the ability of the jth student in ith class. The number is between 0 and 10^9, inclusive.
Output
Output the minimal difference one can achieve by choosing the representative from each class.
Example
Input: 3 4 12 16 67 43 7 17 68 48 14 15 77 54 Output: 2
Input: 4 3 10 20 30 40 50 60 70 80 90 100 110 120 Output: 70
hide comments
binhbocnc:
20220717 11:26:54
nice problem :D


makhan_28:
20210316 18:27:20
Good problem on two pointer :)


fawad:
20200629 15:36:13
2.35 Time ac. Last edit: 20200629 16:50:34 

c_jain:
20180220 14:02:09
solution took 1.05 sec and still accepted!!!!! :) Last edit: 20180220 14:02:30 

hulk_baba:
20170612 06:33:11
My solution took 3.59 seconds and still got Accepted !!! How?


Liquid_Science:
20160112 15:45:48
this is hard in java :( got the logic but tle 

kejriwal:
20151024 00:21:42
nice one :D 

Anirudh Goyal:
20130103 21:05:42
Nice one :)


akb:
20120613 16:00:10
OMG!nice problem......:) 
Added by:  Lawl 
Date:  20110601 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  2011 KOI regional 