#include <iostream>
#include <algorithm>
using namespace std;
#define lson (mid << 1)
#define rson (mid << 1 | 1)
const int maxn = 1e5 + 10;
const int inf = 1e9;
int n, m, k, l[maxn], r[maxn], L[maxn << 1], b[maxn << 1];
struct lzcy {
	int k, cur;
	lzcy(int a = 0, int b = 0) {k = a; cur = b;}
	inline lzcy operator+(const lzcy& r) const {
		return {k + r.k, cur + r.cur};
	}
	inline bool operator<(const lzcy& r) const {
		return cur == r.cur ? k > r.k : cur < r.cur;
	}
	inline lzcy operator-(const int x) const {
		return {k, cur - x};
	}
} f[maxn << 1], s[maxn << 1], c[maxn << 2];
void chmin(int& a, int b) {a = min(a, b);}
void build(int k, int l, int r) {
	c[k] = {inf, -inf}; if (l == r) return;
	int mid = (l + r) >> 1; build(lson, l, mid); build(rson, mid + 1, r);
}
void update(int k, int l, int r, int p, lzcy v) {
	if (l == r) {c[k] = v; return;}
	int mid = (l + r) >> 1;
	if (p <= mid) update(lson, l, mid, p, v);
	else update(rson, mid + 1, r, p, v);
	c[k] = max(c[lson], c[rson]);
}
lzcy query(int k, int l, int r, int L, int R) {
	if (L <= l && r <= R) return c[k];
	int mid = (l + r) >> 1; lzcy nerd(inf, -inf);
	if (L <= mid) nerd = max(nerd, query(lson, l, mid, L, R));
	if (R > mid) nerd = max(nerd, query(rson, mid + 1, r, L, R));
	return nerd;
}
bool check(int x) {
	build(1, 1, m); for (int i = 1; i <= m; i++)
		f[i] = max(query(1, 1, m, L[i], i) + lzcy(1, b[i] - x), s[L[i] - 1] + lzcy(1, b[i] - b[L[i]] - x)),
		s[i] = max(s[i - 1], f[i]), update(1, 1, m, i, f[i] - b[i]);
	return s[m].k <= k;
}
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> k; k = n - k;
	for (int i = 1; i <= n; i++) cin >> l[i] >> r[i], b[++m] = l[i], b[++m] = r[i];
	sort(b + 1, b + m + 1); m = unique(b + 1, b + m + 1) - b - 1;
	for (int i = 1; i <= m; i++) L[i] = i;
	for (int i = 1; i <= n; i++) chmin(L[lower_bound(b + 1, b + m + 1, r[i]) - b], lower_bound(b + 1, b + m + 1, l[i]) - b);
	int l = 0, r = inf, res = inf;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid - 1, res = mid;
		else l = mid + 1;
	}
	check(res); cout << s[m].cur + res * k << '\n';
	return 0;
}