#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen(".inp", "r"))
		assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout));
#else
	using namespace chrono;
	auto start = steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = steady_clock::now();
	cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

const int N = 1e5 + 5;

int n, m, k, L[N], R[N], dp[N], p[N], dq[N];
vector<int> vals, seg[N];

int st[N << 2], lz[N << 2];

#define tm ((tl + tr) >> 1)
#define left id << 1, tl, tm
#define right id << 1 | 1, tm + 1, tr

void build(int id = 1, int tl = 0, int tr = m - 1) {
	if (tl == tr) {
		st[id] = dq[tl], lz[id] = 0;
	} else {
		build(left), build(right);
		st[id] = max(st[id << 1], st[id << 1 | 1]), lz[id] = 0;
	}
}

inline void apply(int id, int v) {
	st[id] += v, lz[id] += v;
}
inline void push(int id) {
	if (lz[id]) apply(id << 1, lz[id]), apply(id << 1 | 1, lz[id]), lz[id] = 0;
}

void update(int l, int r, int v, int id = 1, int tl = 0, int tr = m - 1) {
	if (l > tr || tl > r) return ;
	if (l <= tl && tr <= r) return apply(id, v);
	push(id), update(l, r, v, left), update(l, r, v, right);
	st[id] = max(st[id << 1], st[id << 1 | 1]);
}

int query(int l, int r, int id = 1, int tl = 0, int tr = m - 1) {
	if (l > tr || tl > r) return -1e9;
	if (l <= tl && tr <= r) return st[id];
	return push(id), max(query(l, r, left), query(l, r, right));
}


#undef tm
#undef left
#undef right

void Hollwo_Pelw(){
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> L[i] >> R[i], ++ R[i];
		vals.push_back(L[i]);
		vals.push_back(R[i]);
	}

	sort(vals.begin(), vals.end());
	vals.resize(m = unique(vals.begin(), vals.end()) - vals.begin());

	for (int i = 1; i <= n; i++) {
		L[i] = lower_bound(vals.begin(), vals.end(), L[i]) - vals.begin();
		R[i] = lower_bound(vals.begin(), vals.end(), R[i]) - vals.begin();
		seg[R[i]].push_back(L[i]);
	}

	for (int i = 1; i <= n; i++)
		p[L[i]] ++;
	for (int i = m; i >= 1; i--)
		p[i - 1] += p[i];

	memset(dq, -0x3f, sizeof dq);
	dq[0] = 0;

	int ans = 0;

	while (k --) {
		build();
		// cout << "FUCK\n";
		for (int i = 0; i < m; i++) {
			// cout << "v = " << vals[i] << '\n';
			for (int j : seg[i]) {
				// for (int k = 0; k < j; k++)
				// 	update(k, k, -1);
				update(0, j - 1, -1);
			}
			// for (int j = 0; j < m; j++)
			// 	cout << query(j, j) << " \n"[j == m - 1];
			dp[i] = query(0, i);

			ans = max(ans, dp[i] - p[i + 1] + n);
		}
		// for (int i = 0; i < m; i++)
		// 	cout << vals[i] << " -> " << dp[i] << '\n';

		for (int i = 0; i < m; i++)
			dq[i] = dp[i];
	}

	cout << ans << '\n';
}