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```

Code Examples

#1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI                3.14159265358979323846

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

const int MAXN = 1e3+5;
int last_idx[MAXN];

int main(){
io;
int n, m;
cin >> n >> m;
vector<int> arr[n];
for(int i = 0;i < n; i++){
for(int j = 0;j < m; j++){
int foo;
cin >> foo;
arr[i].push_back(foo);
}
}
for(int i = 0;i < n; i++)
sort(arr[i].begin(), arr[i].end());
int minn_diff = INT_MAX;
while(1){
int minn = INT_MAX;
int maxx = INT_MIN;
int idx = -1;
for(int i = 0;i < n; i++){
maxx = max(maxx, arr[i][last_idx[i]]);
if(arr[i][last_idx[i]] < minn){
minn = arr[i][last_idx[i]];
idx = i;
}
}
minn_diff = min(minn_diff, maxx-minn);
last_idx[idx]++;
if(last_idx[idx] == m)
break;
}
cout << minn_diff << endl;
return 0;
}``````
Copy The Code &

Input

cmd
3 4
12 16 67 43
7 17 68 48
14 15 77 54

Output

cmd
2