#ifndef MyGO
#define MyGO
#include MyGO __FILE__ MyGO

void solve() {
    int N, K; cin >> N >> K;

    vector<pii> itv(N);
    for (int i = 0; i < N; ++i) {
        cin >> itv[i].first >> itv[i].second;
        itv[i].first  = itv[i].first  * N;
        itv[i].second = itv[i].second * N + i;
    }
    sort(ALL(itv), [&](pii &p1, pii &p2) { return p1.second < p2.second; });

    vector<int> l_dec_id(N); iota(ALL(l_dec_id), 0);
    sort(ALL(l_dec_id), [&](int x, int y) {
        return itv[x].first > itv[y].first;
    });
    // debug(l_dec_id);

    vector cost(N, vector<int>(N, 0));
    for (int i = 0; i < N; ++i) {
        int cnt = 0, tok = 0;
        while (tok < N and itv[l_dec_id[tok]].first > itv[i].second) {
            ++tok;
        }
        for (int j = i-1; j >= 0; --j) {
            while (tok < N and itv[l_dec_id[tok]].first > itv[j].second) {
                cnt += (l_dec_id[tok] >= i), ++tok;
            }
            cost[j][i] = cnt;
        }
        while (tok < N) {
            cnt += (l_dec_id[tok] >= i), ++tok;
        }
        cost[i][i] = cnt;
    }

    // for (int i = 0; i < N; ++i) for (int j = 0; j < i; ++j) {
    //     int cnt = 0;
    //     for (int p = 0; p < N; ++p) {
    //         cnt += (itv[j].second < itv[p].first and itv[p].first <= itv[i].second and itv[i].second <= itv[p].second);
    //     }
    //     // debug(i, j, cost[j][i], cnt);
    //     assert(cnt == cost[j][i]);
    // }

    auto recur = [&](auto &dp_now, auto &dp_lst, int lstL, int lstR, int nowL, int nowR, auto &&self) -> void {
        if (nowL > nowR) return;
        // debug(nowL, nowR, lstL, lstR);
        int nowM = (nowL + nowR) >> 1, lstM = lstL;
        for (int M = lstL; M <= min(lstR, nowM-1); ++M) {
            if (chmax(dp_now[nowM], dp_lst[M] + cost[M][nowM])) lstM = M;
        }
        self(dp_now, dp_lst, lstL, lstM, nowL, nowM-1, self);
        self(dp_now, dp_lst, lstM, lstR, nowM+1, nowR, self);
    };

    vector dp(2, vector<int>(N, 0));
    for (int k = 1; k <= K; ++k) {
        for (int i = 0; i < N; ++i) dp[k&1][i] = cost[i][i];
        recur(dp[k&1], dp[(k^1)&1], 0, N-1, 1, N-1, recur);
        // debug(k, dp[k&1]);
    }
    cout << *max_element(ALL(dp[K&1])) << "\n";
}

int32_t main() {
    fastIO();
    
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

#else

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
#define int i64
using pii = pair<int, int>;

#define ee emplace
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

template <typename T>
ostream& operator << (ostream &os, const vector<T> &vec) {
    for (int i = 0; i < SZ(vec); ++i) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}

#ifdef local
#define fastIO() void()
#define debug(...) \
    fprintf(stderr, "\u001b[33m"), \
    fprintf(stderr, "Line %d: (%s) = ", __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), \
    fprintf(stderr, "\u001b[0m")
template <typename T> void _do(T &&_t) { cerr << _t << "\n"; }
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) { cerr << _t << ", ", _do(_u...); }
#else
#define fastIO() cin.tie(0)->sync_with_stdio(0)
#define debug(...) void()
#endif

template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
template <typename T, typename U> bool chmax(T &lhs, U rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; }

#endif