#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); i--)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

struct SegTree
{
	int n;
	vector<int> mx, add;
	
	void init(int _n)
	{
		n = 2 << (32 - __builtin_clz(_n));
		mx.assign(n, 0);
		add.assign(n, 0);
	}
	void push(int v, int tl, int tr)
	{
		mx[v] += add[v];
		if(tl + 1 != tr)
		{
			FOR(t, 1, 3)
				add[2 * v + t] += add[v]; 
		}
		add[v] = 0;
	}
	void upd(int v, int tl, int tr, int l, int r, int val)
	{
		//cout << v << " " << tl << " " << tr << endl;
		push(v, tl, tr);
		if(r <= tl || tr <= l)
			return;
		if(l <= tl && tr <= r)
		{
			add[v] = val;
			push(v, tl, tr);
			return;
		}
		int tm = (tl + tr) / 2;
		upd(2 * v + 1, tl, tm, l, r, val);
		upd(2 * v + 2, tm, tr, l, r, val);
		
		mx[v] = max(mx[2 * v + 1], mx[2 * v + 2]);
	}	
};

const int N = 1 << 19;
vector<PII> events[N];

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cout << fixed << setprecision(15);
	
	int n, k;
	cin >> n >> k;
	VI poses;
	vector<PII> arr(n);
	FOR(i, 0, n)
	{
		cin >> arr[i].F >> arr[i].S;
		poses.PB(arr[i].F);
	}
	sort(ALL(poses));
	poses.resize(unique(ALL(poses)) - poses.begin());
	FOR(i, 0, n)
	{
		arr[i].F = (lower_bound(ALL(poses), arr[i].F) - poses.begin());
		arr[i].S = (upper_bound(ALL(poses), arr[i].S) - poses.begin());
		
		events[arr[i].F + 1].PB(MP(arr[i].F + 1, 1));
		events[arr[i].S + 1].PB(MP(arr[i].F + 1, -1));
	}
	
	n = SZ(poses) + 1;
	int ans = k;
	VI dp0(n, 0);
	
	
	FOR(draws, 1, k + 1)
	{
		SegTree T;
		T.init(n);
		FOR(i, 0, n)
		{
			T.upd(0, 0, n, i, i + 1, dp0[i]);
		}
	
		VI dp1(n, 0);
		FOR(i, 0, n)
		{
			for(auto [r, val] : events[i])
			{
				assert(r <= n);
				T.upd(0, 0, n, 0, r, val);
			}
			T.push(0, 0, n);
			dp1[i] = T.mx[0];
			ans = max(ans, dp1[i]);
		}
		dp0 = dp1;
		//FOR(i, 0, n)
		//	cout << dp1[i] << " ";
		//cout << endl;
	}
	cout << min(ans, n) << "\n";

	
	
	
	
	return 0;
}