#include<bits/stdc++.h> #include<bits/extc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} const int MAXN=2000010,inf=1e18; int n,m,p[MAXN],k,q[MAXN]; pii a[MAXN],f[MAXN],g[MAXN]; bool cmp(pii x,pii y){return x.sc<y.sc;} deque<int>Q; pii check(int x){ while(!Q.empty())Q.pop_back(); f[0]=g[0]={0,0}; for(int i=1;i<=k;i++){ while(!Q.empty()&&Q.front()<q[i])Q.pop_front(); f[i]=max({f[i-1],mk(f[q[i]-1].fr+p[i]-p[q[i]]+1-x,f[q[i]-1].sc+1)}); if(!Q.empty())f[i]=max(f[i],{g[Q.front()].fr+p[i]-x,g[Q.front()].sc+1}); g[i]=mk(f[i].fr-p[i],f[i].sc); while(!Q.empty()&&g[Q.back()]<g[i])Q.pop_back(); Q.push_back(i); } return f[k]; } void slv(){ n=read(),m=read(); for(int i=1;i<=n;i++)a[i].fr=read(),a[i].sc=read()-1; for(int i=1;i<=n;i++)if(a[i].fr<=a[i].sc)p[++k]=a[i].fr,p[++k]=a[i].sc; sort(p+1,p+k+1);k=unique(p+1,p+k+1)-p-1; for(int i=1;i<=n;i++)if(a[i].fr<=a[i].sc)a[i].fr=upper_bound(p+1,p+k+1,a[i].fr)-p-1,a[i].sc=upper_bound(p+1,p+k+1,a[i].sc)-p-1; for(int i=1;i<=k+1;i++)q[i]=i; for(int i=1;i<=n;i++)if(a[i].fr<=a[i].sc)q[a[i].sc]=min(q[a[i].sc],a[i].fr); for(int i=k;i>=1;i--)q[i]=min(q[i],q[i+1]); int l=0,r=inf,ans=0; while(l<r){ int mid=(l+r+1)>>1; pii tmp=check(mid); if(tmp.sc>=m)l=mid; else r=mid-1; } ans=check(l).fr+l*m; printf("%lld",ans); } signed main(){ // freopen("minion.in","r",stdin);freopen("minion.out","w",stdout); slv(); // cerr<<(clock()*1.0)/CLOCKS_PER_SEC<<"s"<<endl; return 0; }