#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = (int) 1e4 + 5;

pair<int, int> P[MAXN];
int n, m, k;

void compress() {
	vector<int> vals;
	
	for (int i = 1; i <= n; i++) {
		vals.push_back(P[i].first);
		vals.push_back(P[i].second);
	}
	
	sort(vals.begin(), vals.end());
	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
	
	for (int i = 1; i <= n; i++) {
		P[i].first = lower_bound(vals.begin(), vals.end(), P[i].first) - vals.begin();
		P[i].second = lower_bound(vals.begin(), vals.end(), P[i].second) - vals.begin();
	}
	
	m = vals.size();
};

vector<int> dp[MAXN];
vector<int> ev[MAXN];
int T[MAXN];

int t[MAXN * 2];
int e[MAXN * 2];

void build(int v, int tl, int tr) {
	e[v] = 0;
	t[v] = 0;
	
	if (tl == tr) {
		t[v] = T[tl];
		return;
	}
	
	int mid = (tl + tr) >> 1;
	int c1 = v + 1, c2 = v + (mid + 1 - tl) * 2;
	
	build(c1, tl, mid);
	build(c2, mid + 1, tr);
	
	t[v] = max(t[c1], t[c2]); 
}

void push(int v, int tl, int tr) {
	if (e[v] == 0) {
		return;
	}
	
	if (tl != tr) {
		int mid = (tl + tr) >> 1;
		int c1 = v + 1, c2 = v + (mid + 1 - tl) * 2;
		e[c1] += e[v];
		e[c2] += e[v];
	}
	
	t[v] += e[v];
	e[v] = 0;
}

void update(int v, int tl, int tr, int l, int r, int x) {
	push(v, tl, tr);
	
	if (l > r || tl > r || tr < l) {
		return;
	}
	
	if (l <= tl && tr <= r) {
		e[v] += x;
		push(v, tl, tr);
		return;
	}
	
	int mid = (tl + tr) >> 1;
	int c1 = v + 1, c2 = v + (mid + 1 - tl) * 2;
	
	update(c1, tl, mid, l, r, x);
	update(c2, mid + 1, tr, l, r, x);
	
	t[v] = max(t[c1], t[c2]);
}

int query(int v, int tl, int tr, int l, int r) {
	push(v, tl, tr);
	
	if (l > r || tl > r || tr < l) {
		return 0;
	}
	
	if (l <= tl && tr <= r) {
		return t[v];
	}
	
	int mid = (tl + tr) >> 1;
	int c1 = v + 1, c2 = v + (mid + 1 - tl) * 2;
	
	return max(
		query(c1, tl, mid, l, r),
		query(c2, mid + 1, tr, l, r)
	);
}

void trav(int v, int tl, int tr) {
	push(v, tl, tr);
	
	if (tl == tr) {
		cout << t[v] << ' ';
		return;
	}
	
	int mid = (tl + tr) >> 1;
	int c1 = v + 1, c2 = v + (mid + 1 - tl) * 2;
	
	trav(c1, tl, mid);
	trav(c2, mid + 1, tr);
	
	t[v] = max(t[c1], t[c2]);
}

void dbg(string s) {
	return;
	cout << s << ": ";
	trav(1, 0, m - 1);
	cout << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); 	
	
	cin >> n >> k;
	
	for (int i = 1; i <= n; i++) {
		cin >> P[i].first >> P[i].second;
	}
	
	compress();
	
	for (int i = 0; i < m; i++) {
		dp[i] = vector<int>(m, 0);
	}
	
	for (int i = 1; i <= n; i++) {
		ev[P[i].first].push_back(i);
		ev[P[i].second + 1].push_back(-i);
	}
	
	for (int lvl = 1; lvl <= k; lvl++) {
		for (int i = 0; i < m; i++) {
			T[i] = (i > 0 ? dp[lvl - 1][i - 1] : 0);
		}
		
		build(1, 0, m - 1);
		
		for (int i = 0; i < m; i++) {	
			for (int id: ev[i]) {
				if (id > 0) {
					dbg("before: ");
					int p = P[id].first;
					update(1, 0, m - 1, 0, p, 1);
					dbg("after: ");
				}
				else {
					int p = P[-id].first;
					update(1, 0, m - 1, 0, p, -1);
				}
			}
			
			dp[lvl][i] = query(1, 0, m - 1, 0, i);
		}
	}
	
	int ans = 0;
	
	for (int lvl = 1; lvl <= k; lvl++) {
		for (int i = 0; i < m; i++) {
			ans = max(ans, dp[lvl][i]);
		}
	}
	
	cout << ans << '\n';
	return 0;
}