#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=1e6+10; pll a[N],b[N]; int n,m,tot=0; //ll f[N][N],c[N][N],mx[N]; int it[N]; pll f[N]; void DP(ll val,int op=0){ for(int i=1;i<=n;i++) f[i]=mk(-1e18,-1e18); f[0]=mk(0,0);pll mx=f[0]; int it=0; for(int i=1;i<=n;i++){ while(it<i){ if(b[it].se>b[i].fi) break; mx=max(mx,f[it]); it++; }pll p1=mx,p2=f[it]; p1.se--;p1.fi+=b[i].se-b[i].fi-val; p2.se--;p2.fi+=b[i].se-b[it].se-val; f[i]=max(p1,p2); f[i]=max(f[i],f[i-1]); //if(op==1) cout<<f[i].fi<<' '<<f[i].se<<endl; //if(op==1) cout<<b[i].se-b[i].fi-val<<endl; } } 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; //cout<<a[i].fi<<' '<<a[i].se<<endl; } } if(tot==0){cout<<0<<endl;return 0;} b[0]=mk(0,0);m=min(m,tot); ll l=0,r=(1e18/tot)+100; while(l<r){ ll mid=(l+r)/2; DP(mid); if(-f[n].se<=m) r=mid; else l=mid+1; }DP(l,1); cout<<f[n].fi+m*l<<endl; return 0; }