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 17-15 = 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: 2022-07-17 11:26:54

nice problem :D

makhan_28: 2021-03-16 18:27:20

Good problem on two pointer :)

fawad: 2020-06-29 15:36:13

2.35 Time ac.

Last edit: 2020-06-29 16:50:34
c_jain: 2018-02-20 14:02:09

solution took 1.05 sec and still accepted!!!!! :)

Last edit: 2018-02-20 14:02:30
hulk_baba: 2017-06-12 06:33:11

My solution took 3.59 seconds and still got Accepted !!! How?

Liquid_Science: 2016-01-12 15:45:48

this is hard in java :( got the logic but tle

kejriwal: 2015-10-24 00:21:42

nice one :D

Anirudh Goyal: 2013-01-03 21:05:42

Nice one :)

akb: 2012-06-13 16:00:10

OMG!nice problem......:)


Added by:Lawl
Date:2011-06-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:2011 KOI regional