Offline classes have started and now everyone is coming to college. Peter decided to impress exactly n girls on campus by buying one gift for each of them i.e. each girl will receive exactly one gift.
There are m stores in and around the college campus, in each of which he can buy a gift for any girl.

We are given an m*n matrix, H, where H[i][j] denotes the units of happiness of the j-th girl if a gift for her is bought from the i-th store.

Peter has to write assignments and so he decided to only visit at most n−1 stores out of m stores (where n is the number of girls he wants to impress).

Let the j-th girl receive Aj units of happiness from Peter's gift and let f = min{A1,A2,...,An}
Help Peter choose gifts so that the value of f is as high as possible.

image

Input Format

The first line contains two integer m and n denoting number of shops and number of girls to impress respectively.
Then m lines follow, each containing n numbers.

Constraints

n>=2
2<= m*n <=10e5
1<= H[i][j] <=10e9

Output Format

The maximum possible value of f

Sample Input 0

4 3
1 3 1
3 1 1
1 2 2
1 1 3
Sample Output 0

2
Explanation 0

For girl 1,gift can be bought from store 2 i.e H[2][1] = 3(A1).
For girl 2,gift can be bought from store 3 i.e H[3][2] = 2(A2).
For girl 3,gift can be bought from store 3 i.e H[3][3] = 2(A3).
f = min{A1,A2,A3} = 2

Sample Input 1

2 4
6 5 2 1
7 9 7 2
Sample Output 1

2
Explanation 1

For girl 1,gift can be bought from store 2 i.e H[2][1] = 7(A1).
For girl 2,gift can be bought from store 2 i.e H[2][2] = 9(A2).
For girl 3,gift can be bought from store 1 i.e H[1][3] = 2(A3).
For girl 4,gift can be bought from store 2 i.e H[2][4] = 2(A4).
f = min{A1,A2,A3,A4} = 2

Contest ends in 2 hours
Submissions: 16
Max Score: 40
Difficulty: Hard
Rate This Challenge:

More

1
#include <bits/stdc++.h>
2
using namespace std;
3
​
4
​
5
​
6
int maximiseHappiness(int m,int n,vector<vector> &H){
7

8
//solve here
9
}
10
​
11
int main(){
12
​
13
int m,n;
14
cin >> m >> n;
15
vector<vector> H(m,vector (n,0));
16
​
17
for(int i=0;i<m;i++)
18
{
19
for(int j=0;j<n;j++)
20
{
21
cin >> H[i][j];
22
}
23
}
24
​
25
int result = maximiseHappiness(m,n,H);
26
cout << result << "\n";
27
​
28
}