#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define fi first #define se second #define mk make_pair using namespace std; const int N=3050; pll a[N],b[N]; int n,m,tot=0; ll f[N][N],c[N][N],mx[N]; int it[N]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i].fi>>a[i].se; sort(a+1,a+n+1,[&](pll a,pll b){ if(a.fi==b.fi) return a.se>b.se; return a.fi<b.fi; }); ll mr=0; for(int i=1;i<=n;i++){ if(a[i].se>mr&&a[i].fi<a[i].se){ b[++tot]=a[i]; mr=a[i].se; } } if(tot==0){cout<<0<<endl;return 0;} b[0]=mk(0,0); memset(c,0xc0,sizeof(c)); for(int i=0;i<=tot;i++){ for(int j=i+1;j<=tot;j++){ c[i][j]=b[j].se-max(b[j].fi,b[i].se); } } memset(mx,0xc0,sizeof(mx)); memset(f,0xc0,sizeof(f)); f[0][0]=0; /*for(int i=1;i<=tot;i++){ for(int j=1;j<=m;j++){ for(int k=0;k<i;k++){ f[i][j]=max(f[i][j],f[k][j-1]+c[k][i]); } } }*/ for(int i=1;i<=tot;i++){ for(int j=1;j<=m;j++){ while(it[j]<i){ if(b[it[j]].se>b[i].fi) break; mx[j]=max(mx[j],f[it[j]][j-1]); it[j]++; }f[i][j]=max(f[it[j]][j-1]+b[i].se-b[it[j]].se,mx[j]+b[i].se-b[i].fi); //cout<<i<<' '<<j<<' '<<f[i][j]<<endl; } } ll ans=0; for(int i=1;i<=m;i++){ ans=max(ans,f[tot][i]); }cout<<ans<<endl; return 0; }