给定若干区间，你可以删除 $k$ 个区间，使得剩下的区间覆盖总长尽量大。

$n\le 10^5,k\le \min(n,100)$。

纪念一下闷头做了一下午 + 一晚上的题。

首先发现一件事情，被其他区间包含的区间一定不优，可以提前删掉，这样我们的区间就变成了端点单调区间。

于是我们可以把区间排序。

考虑 $dp$，设 $f_{k,j,i}$ 为考虑了前 $k$ 个区间，删掉了 $j$ 个，最后一个选的是 $i$。

方程是朴素的：

$$f_{k,j+1,i}\gets f_{k-1,j,i}\\f_{k,j,k}\gets f_{k-1,j,i}+r_k-\max(l_k,r_i)$$

复杂度 $O(n^2k)$，非常的菜。

接下来你发现第一个转移实际上就是把 $f_{k-1,j}$ 复制到 $f_{k,j+1}$，那我们不妨规定每次 $k-1\to k$，我们都 $j\to j+1$。

也就是每次 $k$ 跑一步的时候，我们就掩耳盗铃，把 $f_j$ 当作本来的 $f_{j+1}$。

也就相当于原来的转移终点的 $j$ 都变成了 $j-1$。

把转移柿子重新写一下：

$$f_{j-1,k}\gets f_{j,i}+r_k-\max(l_k,r_i)$$

（由于你掩耳盗铃，就直接在原来的数组上 $dp$，不需要第一维了。）

不难发现原来的 $j$ 最多到 $100$，所以一个 $j$ 连续加 $100$ 轮 $1$ 就没有意义了，在我们的新意义下就是停在原地 $100$ 轮就没有意义了，所以我们在 $\bmod \ 100$ 意义下处理 $j$ 这一维。

而原来没有意义的部分要不要清空呢？

不需要，本题取的是 $\max$，之前的部分选的区间很少，一定不优。

然后我们就把空间复杂度压缩到了 $O(nk)$，复杂动态规划优化的第一步往往是先把空间压到合适的地方再时间优化。

接下来我们观察这个柿子（写成填表的形式）：

$$f_{j,k}\gets \max(f_{j+1,i}+r_k-\max(l_k,r_i))$$

不难发现可以分类讨论内层的 $\max$：

$$f_{j,k}\gets \max\left(\max_{i}^{r_i\le l_i}\{f_{j+1,i}+r_k-l_k\},\max_{i}^{r_i>l_k}\{f_{j+1,i}+r_k-r_i\}\right)$$

那就可以把无关项提出来了：

$$f_{j,k}\gets \max\left(\max_{i}^{r_i\le l_i}\{f_{j+1,i}\}+r_k-l_k,\max_{i}^{r_i>l_k}\{f_{j+1,i}-r_i\}+r_k\right)$$

于是我们要做的相当于两个区间 $\max$，可以用主流数据结构做到 $O(\log n)$ 插入和查询，但这不够。

我们进一步观察，发现第一个是前缀 $\max$，可以自然维护。

第二个是区间 $\max$，但我们插入的顺序和询问的顺序具有单调性，可以开 $100$ 个单调队列自然维护。

还有这种写法比较卡空间，记得开 int，并且不要开多余数组，可以以 $\text{121.4MB}$ 的擦边空间通过。

#include<bits/stdc++.h>
#define fd(x) (lower_bound(V+1,V+vnt+1,x)-V)
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
using namespace std;typedef int ll;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char *p1,*p2,buf[1<<21];
int read() {
	int s=0,w=0;char ch=gc();
	while(ch<'0'||ch>'9') w|=(ch=='-'),ch=gc();
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=gc();
	return w?-s:s;
} const int N=1e5+2,K=102;const ll inf=1e9+5;
int V[N<<1],vnt,n,m,k,ls[N];
ll f[K][N],pmax[K][N],tmp[K];
struct S {
	int l,r;
	bool operator<(S b) {
		return l==b.l?r>b.r:l<b.l;
	}
} s[N],a[N];
struct DL {
	ll q[N];int hd,tl;
	DL() {hd=1;tl=0;}
	void del(int x) {
		while(hd<=tl&&q[hd]<x) hd++;
	}
	void push(ll f[],int x) {
		while(hd<=tl&&f[q[tl]]-V[a[q[tl]].r]<f[x]-V[a[x].r]) tl--;
		q[++tl]=x;
	}
	ll mx(ll f[]) {return hd<=tl?f[q[hd]]-V[a[q[hd]].r]:-inf;}
} q[K];
int main() {
	n=read();m=read();
	F(i,1,n) s[i]={V[++vnt]=read(),V[++vnt]=read()};
	sort(V+1,V+vnt+1);vnt=unique(V+1,V+vnt+1)-V-1;
	F(i,1,n) s[i].l=fd(s[i].l),s[i].r=fd(s[i].r);
	sort(s+1,s+n+1);
	int mxr=0;F(i,1,n) if(mxr<s[i].r) mxr=s[i].r,a[++k]=s[i];
	if(n-k>=m) {
		ll ans=0;F(i,1,k) ans+=V[a[i].r]-V[max(a[i].l,a[i-1].r)];
		cout<<ans<<endl;return 0;
	} 
	F(i,1,k) {
		int L=0,R=i,mid;
		while(L<=R) (a[mid=L+R>>1].r<=a[i].l)?L=mid+1,ls[i]=mid:(R=mid-1);
	}
	memset(f,-0x3f,sizeof f);
	memset(pmax,-0x3f,sizeof pmax);
	f[0][0]=0;pmax[0][0]=0;
	F(i,1,k) {
		F(j,0,99) {int pj=(j+99)%100;
			q[j].del(ls[i]+1);
			tmp[pj]=max(pmax[j][ls[i]]+V[a[i].r]-V[a[i].l],
						q[j].mx(f[j])+V[a[i].r]);
		}
		F(j,0,99) {
			tmp[j]<0&&(tmp[j]=-inf);
			f[j][i]=tmp[j];
			pmax[j][i]=max(pmax[j][i-1],f[j][i]);
			q[j].push(f[j],i);
		}
	} int zm=((-n+m)%100+100)%100;
	cout<<*max_element(f[zm],f[zm]+n+1)<<endl;
	return 0;
}