// Problem: A. a
// Contest: undefined - NOIP2024训练赛 06
// URL: http://www.noi.ac/contest/1158/problem/2031
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define PII pair<int, int>

using namespace std;

const int N = 2e5 + 10, M = 1e6 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f;

int n, m, q, ans;
PII s[N], dp[N];
bool vis[N];

vector<int> e[N];

inline void solve(int st)
{
	int cnt = 0, res = 0;
	for(int i = 0; (1 << i) <= st; i ++)
	{
		if((st >> i) & 1) vis[i + 1] = true, cnt ++;
		else vis[i] = false;
	}
	if(cnt != n - m) return;
	int l = 1, r = 0;
	for(int i = 1; i <= n; i ++)
	{
		if(!vis[i]) continue;
		if(s[i].fi > r) res += (r - l + 1), l = s[i].fi, r = s[i].se;
		else r = max(s[i].se, r);
	}
	res += r - l + 1, ans = max(ans, res); 
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) {cin >> s[i].fi >> s[i].se; s[i].fi ++;}
	sort(s + 1, s + n + 1);
	for(int i = 1; i < (1 << n); i ++) solve(i);
	cout << ans << '\n';
	return 0;
}