Problem: BackGround

In the Demon's Plan, 108 demons who control the desire are competing in the programming contest day and night. The organizer, Patron, is trying to invite the demons to "Rix-Magna", a place where all the souls gather. Patron wants to send an invitation to a demon who hasn't sent an invitation yet, but he decides to let his familiars do it because the demons are all over the world and it's a hassle to go by himself. Patrons are smart and are trying to allocate which familiars are in charge of which demons so that the familiars work more equally.

Problem

There are N familiars and M demons. The distance between familiar i and devil j is Hi j.

I want each demon to have one familiar. Which familiar will visit which demon will be assigned according to the following conditions.

1. Minimize the maximum difference in the number of demons visited per familiar.
2. Minimize the maximum distance between the visiting demon and the familiar familiar after satisfying 1.



Output the maximum difference in the number of visiting demons per familiar on the first line, and the maximum distance between the demon and the familiar in charge on the second line.

Constraints

* 1 ≤ N ≤ 108
* 1 ≤ M ≤ 108
* 1 ≤ Hi j ≤ 109 (0 ≤ i <N, 0 ≤ j <M) (distance from familiar i to devil j)

Input

The input is given in the following format.


N M
H0 0 H0 1… H0 M−1
H1 0 H1 1… H1 M-1
..
..
HN−1 0 HN−1 1… HN−1 M−1


On the first line, the number N of familiars and the number M of demons are given as integers separated by blanks. The distance between the familiar and the devil is given as an integer in the following N lines. Hij represents the distance between familiar i and devil j.

Output

According to the conditions of the problem statement, output the maximum difference in the number of visiting demons per familiar on the first line, and the maximum distance between the demon and the familiar in charge on the second line.

Examples

Input

3 3
1 2 3
2 1 2
3 2 1


Output

0
1


Input

3 5
1 2 3 4 5
5 4 3 2 1
4 3 2 1 5


Output

1
2

Solution (in CPP):

Solution:
#include<iostream>
#include<vector>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<utility>
#include<set>
#include<map>
#include<stack>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef vector<int> vec;
typedef long double ld;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define stop char nyaa;cin>>nyaa;


int max_n;
const int mn = 100000;

struct edge {
	int to, cap, cost, rev;
};

struct MinCostFlow {
	vector<edge> G[mn];
	int par[mn];
	int dist[mn];
	void add_edge(int from, int to, int cap, int cost) {
		G[from].push_back({ to,cap,cost,(int)G[to].size() });
		G[to].push_back({ from, 0, -cost, (int)G[from].size() - 1 });
		max_n = max({ max_n, from + 1, to + 1 });
	}

	int minimum_road(int s, int t) {
		fill(par, par + max_n, -1);
		fill(dist, dist + max_n, mod);
		dist[s] = 0;
		priority_queue<P, vector<P>, greater<P>> q; q.push({ 0,s });
		while (q.size()) {
			P p = q.top(); q.pop();
			int id = p.second;
			if (id == t)continue;
			if (p.first > dist[id])continue;
			rep(j, G[id].size()) {
				if (G[id][j].cap > 0) {
					int to = G[id][j].to;
					int nd = p.first + G[id][j].cost;
					if (nd < dist[to]) {
						dist[to] = nd;
						par[to] = id;
						q.push({ dist[to],to });
					}
				}
			}
		}
		int cur = t;
		while (cur != s) {
			int p = par[cur];
			if (p < 0)return -1;
			rep(j, G[p].size()) {
				if (G[p][j].cap > 0 && G[p][j].to == cur && dist[p] + G[p][j].cost == dist[cur]) {
					G[p][j].cap--;
					G[cur][G[p][j].rev].cap++;
				}
			}
			cur = p;
		}
		return dist[t];
	}
	int minimum_cost_flow(int s, int t, int k) {
		int ret = 0;
		rep(i, k) {
			int z = minimum_road(s, t);
			if (z < 0)return -1;
			ret += z;
		}
		return ret;
	}
};


 void solve() {
	int n, m;
	cin >> n >> m;
	int d[111][111];
	rep(i, n)rep(j, m)cin >> d[i][j];
	int c1 = m / n, c2 = !!(m%n);
	int ok = 1e9, ng = 0;
	while (ok - ng > 1) {
		int mid = (ok + ng) / 2;
		MinCostFlow mc;
		int s = m + n, t = m + n + 1;
		rep(i, n)rep(j, m) {
			if (d[i][j] <= mid) {
				mc.add_edge(i, n + j, 1, 0);
			}
		}
		rep(i, n) {
			mc.add_edge(s, i, c1, 0);
			mc.add_edge(s, i, c2, 1);
		}
		rep(i, m) {
			mc.add_edge(n + i, t, 1, 0);
		}
		int ret = mc.minimum_cost_flow(s, t, m);
		if (ret == m % n)ok = mid;
		else ng = mid;
	}
	cout << c2 << endl;
	cout << ok << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(6);
	solve();
	//stop
		return 0;
}