#include <bits/stdc++.h>

using namespace std;

const int N = 20'000 + 10,
          K = 500 + 10;
int n, k;
pair<int, int> p[N];

vector<int> allValue;

int pref[N][N];
inline int cal(int l, int r) { 
  return pref[r][r] - pref[l - 1][r] - pref[r][l - 1] + pref[l - 1][l - 1];
}

int f[K][N];
void dnc(int l, int r, int lt, int rt, int stage) { 
  if (l > r) return;
  int mid = (l + r) >> 1;

  auto& ret = f[stage][mid];
  int opt = lt;
  for (int i = lt; i <= min(mid, rt); ++i) { 
    int value = f[stage - 1][i - 1] + cal(i, mid);
    if (value > ret) ret = value, opt = i;
  }

  dnc(l, mid - 1, lt, opt, stage);
  dnc(mid + 1, r, opt, rt, stage);
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> k; 
  for (int i = 1; i <= n; ++i) cin >> p[i].first >> p[i].second;

  for (int i = 1; i <= n; ++i) { 
    allValue.push_back(p[i].first);
    allValue.push_back(p[i].second);
  }

  sort(allValue.begin(), allValue.end());
  allValue.erase(unique(allValue.begin(), allValue.end()), allValue.end());

  for (int i = 1; i <= n; ++i) { 
    p[i].first = upper_bound(allValue.begin(), allValue.end(), p[i].first) - allValue.begin();
    p[i].second = upper_bound(allValue.begin(), allValue.end(), p[i].second) - allValue.begin();
    pref[p[i].first][p[i].second] += 1;
  }

  for (int i = 1; i <= (int)allValue.size(); ++i) { 
    for (int j = 1; j <= (int)allValue.size(); ++j) 
      pref[i][j] += pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
  }

  for (int i = 1; i <= k; ++i) dnc(1, allValue.size(), 1, allValue.size(), i);

  int answer = 0;
  for (int i = 1; i <= k; ++i) { 
    for (int j = 1; j <= (int)allValue.size(); ++j) answer = max(answer , f[i][j]);
  }

  cout << answer << "\n";
}