#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using i64 = long long;
using namespace std;
const int N = 2e4 + 5;
// const int B = 340;
// const int M = 5e3 + 5;
// const int base = 1753591;
// const int mod = 998244353;
// const int mod = 1e9 + 7;
// const double pi = acos(-1);

int n, k, m, l[N], r[N];
vector<vector<int>> dp;
vector<int> add[N], del[N];
struct node
{
    int val, tag;
};
vector<vector<node>> st;
#define lc cur << 1
#define rc cur << 1 | 1
void pushdown(int k, int cur)
{
    st[k][lc].tag += st[k][cur].tag;
    st[k][rc].tag += st[k][cur].tag;
    st[k][lc].val += st[k][cur].tag;
    st[k][rc].val += st[k][cur].tag;
    st[k][cur].tag = 0;
}
void pushup(int k, int cur)
{
    st[k][cur].val = max(st[k][lc].val, st[k][rc].val);
}
int query(int k, int cur, int l, int r, int a, int b)
{
    if (a <= l && r <= b)
        return st[k][cur].val;
    if (a > r || b < l)
        return -1e9;
    pushdown(k, cur);
    int mid = l + r >> 1;
    return max(query(k, lc, l, mid, a, b), query(k, rc, mid + 1, r, a, b));
}
void update(int k, int cur, int l, int r, int a, int b, int x)
{
    if (a <= l && r <= b)
    {
        st[k][cur].val += x;
        st[k][cur].tag += x;
        return;
    }
    pushdown(k, cur);
    int mid = l + r >> 1;
    if (a <= mid)
        update(k, lc, l, mid, a, b, x);
    if (b > mid)
        update(k, rc, mid + 1, r, a, b, x);
    pushup(k, cur);
}
void solve()
{
    cin >> n >> k;
    vector<int> tmp{(int)-1e9};
    for (int i = 1; i <= n; i++)
        cin >> l[i] >> r[i], tmp.push_back(l[i]), tmp.push_back(r[i]);
    sort(tmp.begin(), tmp.end());
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    for (int i = 1; i <= n; i++)
    {
        l[i] = lower_bound(tmp.begin(), tmp.end(), l[i]) - tmp.begin();
        r[i] = lower_bound(tmp.begin(), tmp.end(), r[i]) - tmp.begin();
        m = max({m, l[i], r[i]});
        add[l[i]].push_back(i);
        del[r[i]].push_back(i);
    }
    dp.resize(m + 1, vector<int>(k + 1));
    st.resize(k + 1, vector<node>((m + 5) * 4));
    for (int i = 1, cur = 0; i <= m; i++)
    {
        dp[i] = dp[i - 1];
        cur += add[i].size();
        for (int x : add[i])
            for (int j = 0; j <= k; j++)
                update(j, 1, 0, m, l[x], r[x], -1);
        for (int j = 1; j <= k; j++)
            dp[i][j] = max(dp[i][j], cur + query(j - 1, 1, 0, n, 0, i - 1));
        for (int j = 0; j <= k; j++)
            update(j, 1, 0, m, i, i, dp[i][j]);
        cur -= del[i].size();
        for (int x : del[i])
            for (int j = 0; j <= k; j++)
                update(j, 1, 0, m, l[x], r[x], 1);
    }
    cout << dp[m][k] << '\n';
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    cout << fixed << setprecision(10);
    while (t--)
        solve();
}