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 <bits/stdc++.h>
using namespace std;
typedef long long ll;

typedef int Weight;
typedef int Capacity;
struct Edge {
	int src, dst; Capacity cap;
	Edge(int s, int d, Capacity c) : src(s), dst(d), cap(c) {}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

struct Dinic {
	int n, s, t;
	vector<int> level, prog, que;
	vector<vector<Capacity> > cap, flow;
	vector<vector<int> > g;
	Capacity inf;
	Dinic() {}
	Dinic(const Graph &graph)
		: n(graph.size()),
		cap(n, vector<Capacity>(n)), flow(n, vector<Capacity>(n)),
		g(n, vector<int>()), inf((int)1e9) {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < graph[i].size(); j++) {
				const Edge& e = graph[i][j];
				int u = e.src, v = e.dst;
				Capacity c = e.cap;
				add_edge(u, v, c);
			}
		}
	}
	Dinic(int n_) : n(n_), cap(n, vector<Capacity>(n)), flow(n, vector<Capacity>(n)),
		g(n, vector<int>()), inf((int)1e9) {
	}
	void add_edge(int u, int v, Capacity c) {
		cap[u][v] += c; cap[v][u] += c; flow[v][u] += c;
		g[u].push_back(v); g[v].push_back(u);
	}
	void reset() {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				cap[i][j] = flow[i][j] = 0;
			}
			g[i].clear();
		}
	}
	inline Capacity residue(int u, int v) { return cap[u][v] - flow[u][v]; }
	Capacity solve(int s_, int t_) {
		this->t = t_, this->s = s_;
		que.resize(n + 1);
		Capacity res = 0;
		while(levelize()) { prog.assign(n, 0); res += augment(s, inf); }
		return res;
	}
	bool levelize() {
		int l = 0, r = 0;
		level.assign(n, -1); level[s] = 0; que[r++] = s;
		while(l != r) {
			int v = que[l++]; if(v == t) break;
			for(int i = 0; i < g[v].size(); i++) {
				const int& d = g[v][i];
				if(level[d] == -1 && residue(v, d) != 0) {
					level[d] = level[v] + 1; que[r++] = d;
				}
			}
		}
		return level[t] != -1;
	}
	Capacity augment(int v, Capacity lim) {
		Capacity res = 0;
		if(v == t) return lim;
		for(int &i = prog[v]; i < (int)g[v].size(); i++) {
			const int &d = g[v][i];
			if(residue(v, d) == 0 || level[v] >= level[d]) continue;
			const Capacity aug = augment(d, min(lim, residue(v, d)));
			flow[v][d] += aug; flow[d][v] -= aug;
			res += aug; lim -= aug;
			if(lim == 0) break;
		}
		return res;
	}
};

int N, M;
int H[110][110];
int a1[110], a2[110];
int b[110];

bool check(int x) {
	Dinic d(2 * N + M + 4);
	int s1 = 2 * N + M, s2 = s1 + 1, S = s2 + 1, T = S + 1;
	d.add_edge(S, s1, M - M % N);
	d.add_edge(S, s2, M % N);
	for(int i = 0; i < N; i++) {
		d.add_edge(s1, a1[i], M / N);
		d.add_edge(s2, a2[i], 1);
	}
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) {
			if(H[i][j] <= x) {
				d.add_edge(a1[i], b[j], 1);
				d.add_edge(a2[i], b[j], 1);
			}
		}
	}
	for(int i = 0; i < M; i++) {
		d.add_edge(b[i], T, 1);
	}
	return d.solve(S, T) == M;
}


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) {
			cin >> H[i][j];
		}
	}

	int n = 0;
	for(int i = 0; i < N; i++) {
		a1[i] = n++;
		a2[i] = n++;
	}
	for(int i = 0; i < M; i++) {
		b[i] = n++;
	}

	int diff = M % N == 0 ? 0 : 1;
	int ng = 0, ok = 1e9;
	while(abs(ng - ok) / 2) {
		int mid = (ng + ok) / 2;
		if(check(mid)) ok = mid;
		else ng = mid;
	}
	cout << diff << endl;
	cout << ok << endl;
}