吸氧倒是能过（

#include <stdio.h>
#include <deque>
#include <algorithm>
#include <string.h>

inline int min(const int x, const int y) {return x < y ? x : y;}
inline int max(const int x, const int y) {return x > y ? x : y;}
const int MaxN = 100001, INF = 0x3fffffff;
struct Line {
	int l, r;
	inline bool operator < (const Line x) const {return l < x.l;}
} a[MaxN];

std::deque<int> q;
int f[MaxN][101], L[MaxN], R[MaxN], n;

int main() {
	int N, K, ans(-INF), MaxR(-INF);
	memset(f, ~0x3f, sizeof f);
	scanf("%d%d", &N, &K);
	for (int i(1); i <= N; ++ i) scanf("%d%d", &a[i].l, &a[i].r);
	std::sort(a + 1, a + N + 1);
	for (int i(1); i <= N; ++ i) if (a[i].r > MaxR)
	L[++ n] = a[i].l, R[n] = a[i].r, MaxR = a[i].r;
	K -= N - n;
	if (K <= 0) {
		int ans(0), MaxR(L[1]);
		for (int i(1); i <= n; ++ i) ans += R[i] - max(MaxR, L[i]), MaxR = R[i];
		printf("%d", ans);
		return 0;
	}
	for (int i(0); i <= K; ++ i) f[i][i] = 0;
	for (int k(-1); k >= -n; -- k) {
		int x(k + 1), sum(-INF);
		q.clear();
		for (int j(0); j <= min(K, n + k); ++ j) {
			int i(j - k);
			while (q.size() && R[q.front()] <= L[i])
				sum = max(sum, f[q.front()][x + q.front()]), q.pop_front();
			if (R[i - 1] <= L[i]) sum = max(sum, f[i - 1][x + i - 1]);
			else {
				while (q.size() && f[q.back()][x + q.back()] - R[q.back()] <=
				f[i - 1][x + i - 1] - R[i - 1]) q.pop_back();
				q.push_back(i - 1);
			}
			f[i][j] = sum - L[i] + R[i];
			if (q.size()) f[i][j] = max(f[i][j], f[q.front()][x + q.front()] - R[q.front()] + R[i]);
		}
	}
	for (int i(n - K); i <= n; ++ i) ans = max(ans, f[i][K - n + i]);
	printf("%d", ans);
	return 0;
}