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;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cerr<<(#v)<<":";for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;
#define printVS(vs) cerr<<(#vs)<<":"<<endl;for(auto(s):(vs)){cerr<<(s)<< endl;}
#define printVV(vv) cerr<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;}
#define printP(p) cerr<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cerr<<(#vp)<<":"<<endl;for(auto(p):(vp)){cerr<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cerr << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cerr << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1ll << 60;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

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

const int MAX_V = 300;
vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];

void add_edge(int from, int to, int cap) {
    G[from].emplace_back((edge){to, cap, (int)G[to].size()});
    G[to].emplace_back((edge){from, 0, (int)G[from].size() - 1});
}

void bfs(int s) {
    memset(level, -1, sizeof(level));
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (int i = 0; i < G[v].size(); i++) {
            edge &e = G[v][i];
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
    }
}

int dfs(int v, int t, int f) {
    if (v == t) return f;
    for (int &i = iter[v]; i < G[v].size(); i++) {
        edge &e = G[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s, int t) {
    int flow = 0;
    for (;;) {
        bfs(s);
        if (level[t] < 0) return flow;
        memset(iter, 0, sizeof(iter));
        int f;
        while ((f = dfs(s, t, inf)) > 0) {
            flow += f;
        }
    }
}


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

    int n, m;
    cin >> n >> m;
    vvi h(n, vi(m));
    rep(i, n) rep(j, m) cin >> h[i][j];

    auto check = [&](int ma) {
        rep(v, MAX_V) G[v].clear();

        rep(i, n) {
            rep(j, m) {
                if (h[i][j] <= ma) {
                    add_edge(i, j + n, 1);
                }
            }
        }

        const int s1 = n + m;
        const int s2 = n + m + 1;
        const int t = n + m + 2;

        rep(i, n) {
            add_edge(s1, i, m / n);
            add_edge(s2, i, 1);
        }

        rep(j, m) {
            add_edge(j + n, t, 1);
        }

        if (max_flow(s1, t) < (m / n) * n) return false;
        return max_flow(s2, t) == m % n;
    };

    int l = 0, r = 1e9;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        (check(mid) ? r : l) = mid;
    }
    cout << (m % n != 0) << endl;
    cout << r << endl;
}