#include <bits/stdc++.h>
#define int long long
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define pb push_back
using namespace std;
const int N = 5e5 + 10;
struct Node {
    int l, r;
} A[N];
bool cmp(Node &a, Node &b) { return a.l < b.l; }
int n, m, tot, ans;
int L[N], R[N], H[N], cl[N], cr[N];
map<int, int> hsh;
signed main() {
    scanf("%lld%lld", &n, &m);
    rep(i, 1, n) {
        scanf("%lld%lld", &L[i], &R[i]);
        H[++tot] = L[i];
        H[++tot] = R[i];
    }
    sort(H + 1, H + 1 + tot);
    tot = unique(H + 1, H + 1 + tot) - H - 1;
    rep(i, 1, tot) hsh[H[i]] = i;
    rep(i, 1, n) {
        A[i].l = hsh[L[i]];
        A[i].r = hsh[R[i]];
        ++cl[A[i].l];
        ++cr[A[i].r];
    }
    sort(A + 1, A + 1 + n, cmp);
    int r = 0, p = 1;
    while (r < tot) {
        int mx = 0;
        while (p <= n && L[p] <= H[r]) {
            mx = max(mx, R[p]);
            ++p;
        }
        r = hsh[mx];
        ++ans;
    }
    printf("%lld ", ans);
    int now = 0, mn = n + 1;
    rep(i, 1, n) {
        now += cl[i];
        mn = min(mn, now);
        if (i != n) {
            now -= cr[i];
            if (H[i] + 1 != H[i + 1]) {
                mn = min(mn, now);
            }
        }
    }
    printf("%lld\n", n - mn + 1);
    return 0;
}

In file included from /opt/noilinux/usr/include/c++/4.8/algorithm:62:0,
                 from /opt/noilinux/usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:64,
                 from /sandbox/1/a.cpp:1:
/opt/noilinux/usr/include/c++/4.8/bits/stl_algo.h: In instantiation of '_RandomAccessIterator std::__unguarded_partition(_RandomAccessIterator, _RandomAccessIterator, const _Tp&, _Compare) [with _RandomAccessIterator = Node*; _Tp = Node; _Compare = bool (*)(Node&, Node&)]':
/opt/noilinux/usr/include/c++/4.8/bits/stl_algo.h:2296:78:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = Node*; _Compare = bool (*)(Node&, Node&)]'
/opt/noilinux/usr/include/c++/4.8/bits/stl_algo.h:2337:62:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = Node*; _Size = int; _Compare = bool (*)(Node&, Node&)]'
/opt/noilinux/usr/include/c++/4.8/bits/stl_algo.h:5499:44:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = Node*; _Compare = bool (*)(Node&, Node&)]'
/sandbox/1/a.cpp:32:25:   required from here
/opt/noilinux/usr/include/c++/4.8/bits/stl_algo.h:2263:35: error: invalid initialization of reference of type 'Node&' from expression of type 'const Node'
    while (__comp(*__first, __pivot))
                                   ^
/opt/noilinux/usr/include/c++/4.8/bits/stl_algo.h:2266:34: error: invalid initialization of reference of type 'Node&' from expression of type 'const Node'
    while (__comp(__pivot, *__last))
                                  ^
/sandbox/1/a.cpp: In function 'int main()':
/sandbox/1/a.cpp:17:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld", &n, &m);
                              ^
/sandbox/1/a.cpp:19:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld", &L[i], &R[i]);
                                        ^