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  Weight;
struct Edge {
	int src, dest;
	int cap, rev;
	Weight weight;
	bool operator < (const Edge &rhs) const { return weight > rhs.weight; }
};

const int V = 4000;
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
Weight h[V];                //??????????????£???
Weight dist[V];             //???????????¢
int prevv[V], preve[V];  //??´???????????¨??????

void add_edge(Graph &g, int src, int dest, int cap, Weight weight) {
	g[src].push_back(Edge{ src, dest, cap, (int)g[dest].size(), weight });
	g[dest].push_back(Edge{ dest, src, 0, (int)g[src].size() - 1, -weight });
}
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(auto i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const Weight INF = 2147483647;
const Weight ZERO=0;
//????????????double?????????eps?????????
Weight min_cost_flow(Graph &g, int s, int t, int f) {
	Weight res = ZERO;
	memset(h, ZERO, sizeof(h));
	typedef pair<Weight, int> P;
	while (f > 0) {
		priority_queue<P, vector<P>, greater<P> > que;
		fill(dist, dist + V, INF);
		dist[s] = 0;
		que.push(P(ZERO, s));
		while (!que.empty()) {
			P p = que.top(); que.pop();
			const int v = p.second;
			if (dist[v] < p.first) continue;
			REP(i, g[v].size()) {
				Edge &e = g[v][i];
				if (e.cap > 0 && dist[e.dest] > dist[v] + e.weight + h[v] - h[e.dest]) {
					dist[e.dest] = dist[v] + e.weight + h[v] - h[e.dest];
					prevv[e.dest] = v;
					preve[e.dest] = i;
					que.push(P(dist[e.dest], e.dest));
				}
			}
		}
		if (dist[t] == INF) return -1;
		REP(v, V) h[v] = h[v] + dist[v];

		int d = f;
		for (int v = t; v != s; v = prevv[v]) d = min(d, g[prevv[v]][preve[v]].cap);
		f -= d;
		res = res + d * h[t];
		for (int v = t; v != s; v = prevv[v]) {
			Edge &e = g[prevv[v]][preve[v]];
			e.cap -= d;
			g[v][e.rev].cap += d;
		}
	}
	return res;
}

int N, M;
int norma ;
int amari ;
bool check(const int dis, const vector<vector<int>>&diss) {
	const int start=0;
	const int tukai0=start+1;
	const int tukai1=tukai0+N;
	const int akuma=tukai1+N;
	const int goal=akuma+M;
	Graph g(goal+1);
	for (int i = 0; i < N; ++i) {

		add_edge(g, start, tukai0 + i, 108, 0);
	}
	for (int i = 0; i < N; ++i) {
		add_edge(g,tukai0+i,tukai1+i,norma,0);
		add_edge(g,tukai0+i,tukai1+i,1,1);
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (diss[i][j] <= dis) {
				add_edge(g,tukai1+i,akuma+j,1,0);
			}
		}
	}
	for (int j = 0; j < M; ++j) {
		add_edge(g,akuma+j,goal,1,0);
	}
	auto p(min_cost_flow(g,start,goal,M));
	if(p==-1)return false;
	return p<=amari;
}
int main() { cin >> N >> M;
	vector<vector<int>>diss(N,vector<int>(M));
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cin>>diss[i][j];
		}
	}
	norma=M/N;
	amari = M-(M/N)*N;
	int al=0;
	int ar=1e9;
	while (al + 1 != ar) {
		int am((al+ar+1)/2);
		if (check(am, diss)) {
			ar=am;
		}else{
			al=am;
		}
	}
	if(amari==0)cout<<0<<endl;
	else cout<<1<<endl;
	cout<<ar<<endl;
	
	return 0;
}