/*
 * Author       : YangDavid
 * Created Time : 2019年09月25日 星期三 11时03分44秒
 */

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 1; i <= n; ++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;

#define Type int
struct Edge {
    int from, to;
    Type cap, flow;
    Edge(int u = 0, int v = 0, Type c = 0):
        from(u), to(v), cap(c), flow(0) { }
};

struct Dinic {
    int N;
    vector<Edge> edges;
    vector< vector<int> > adj;
    vector<int> d, cur;

    Dinic(int Num): N(Num + 20), edges(0), adj(Num + 20), d(Num + 20), cur(Num + 20) { }

    void AddEdge(int u, int v, Type cap) {
        if(u == v) return;
        edges.emplace_back(u, v, cap);
        adj[u].emplace_back(edges.size() - 1);
        edges.emplace_back(v, u, 0);
        adj[v].emplace_back(edges.size() - 1);
    }

    bool BFS(int S, int T) {
        queue<int> q({S});
        fill(d.begin(), d.end(), N + 1);
        d[S] = 0;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            if(u == T) break;
            for(int k : adj[u]) {
                Edge &e = edges[k];
                if(e.flow < e.cap && d[e.to] > d[e.from] + 1) {
                    d[e.to] = d[e.from] + 1;
                    q.emplace(e.to);
                }
            }
        }
        return d[T] != N + 1;
    }

    Type DFS(int u, int T, Type flow = -1) {
        if(u == T || flow == 0) return flow;
        for(int &i = cur[u]; i < int(adj[u].size()); ++i) {
            Edge &e = edges[adj[u][i]];
            Edge &re = edges[adj[u][i] ^ 1];
            if(d[e.to] == d[e.from] + 1) {
                Type rem = e.cap - e.flow;
                if(flow != -1 && rem > flow) rem = flow;
                Type pushed = DFS(e.to, T, rem);
                if(pushed > 0) {
                    e.flow += pushed;
                    re.flow -= pushed;
                    return pushed;
                }
            }
        }
        return 0;
    }

    Type MaxFlow(int S, int T) {
        Type total = 0;
        while(BFS(S, T)) {
            fill(cur.begin(), cur.end(), 0);
            while(Type flow = DFS(S, T))
                total += flow;
        }
        return total;
    }
};
#undef Type

const int maxn = 444;
int n, m, l[maxn], r[maxn];
vector<int> ddl[maxn];

int maxPlan() {
    int ans = 0;
    rep(i, n) ddl[l[i]].push_back(r[i]);
    priority_queue<int, vector<int>, greater<int> > works;
    for(int i = 1; i <= 400; ++i) {
        for(auto g : ddl[i]) works.push(g);
        while(!works.empty() && works.top() < i) works.pop();
        if(!works.empty()) ans++, works.pop();
    }
    return ans;
}

int minPlan() {
    Dinic d(800 + n + 2);
    int s = 800 + n + 1, t = 800 + n + 2;
    rep(i, 400) d.AddEdge(i, 400 + i, 1);
    for(int i = 1; i <= m; ++i) {
        d.AddEdge(s, 800 + i, 1);
        for(int j = l[i]; j <= r[i]; ++j)
            d.AddEdge(800 + i, j, 1);
    }
    for(int i = m + 1; i <= n; ++i) {
        d.AddEdge(800 + i, t, 1);
        for(int j = l[i]; j <= r[i]; ++j)
            d.AddEdge(400 + j, 800 + i, 1);
    }
    return d.MaxFlow(s, t);
}
int main() {
    scanf("%d%d", &n, &m);
    rep(i, n) scanf("%d%d", &l[i], &r[i]);
    printf("%d\n%d\n", maxPlan(), minPlan());
    return 0;
}



Measured memory_bytes: 5372