#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef __int128 ll; const int maxn=1e6+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m; struct nd { ll l,r; }d[maxn],t[maxn]; bool operator<(nd a,nd b){ if(a.l!=b.l)return a.l<b.l; return a.r<b.r; } struct node { ll sum;int cnt; }dp[maxn]; bool operator<(node a,node b){ if(a.sum!=b.sum)return a.sum<b.sum; return a.cnt>b.cnt; } node res; int Q[maxn]; node pre[maxn]; bool chk(ll val){ dp[0]=pre[0]={0,0}; res={-1,0}; int l=1,r=0,p=0; up(i,1,n){ while(p<=n&&d[p].r<d[i].l)p++; dp[i]=pre[p-1];dp[i].sum+=d[i].r-d[i].l+1,dp[i].cnt++; while(l<=r&&Q[l]<p)l++; if(l<=r)dp[i]=max(dp[i],(node){dp[Q[l]].sum-d[Q[l]].r+d[i].r,dp[Q[l]].cnt+1}); dp[i].sum-=val; pre[i]=max(pre[i-1],dp[i]); while(l<=r&&(node){dp[Q[r]].sum-d[Q[r]].r,dp[Q[r]].cnt+1}<(node){dp[i].sum-d[i].r,dp[i].cnt+1})r--; Q[++r]=i; //up(k,0,i-1)dp[i]=max(dp[i],(node){dp[k].sum+(d[k].r<d[i].l?d[i].r-d[i].l+1:d[i].r-d[k].r)-val,dp[k].cnt+1}); res=max(res,dp[i]); } return res.cnt<=m; } void slv(){ int nn=0; n=read(),m=read(); up(i,1,n){ ll l=read(),r=read(); if(l<r)++nn,d[nn].l=l,d[nn].r=r; }n=nn; sort(d+1,d+n+1);int top=0; ll mx=0; up(i,1,n)if(mx<d[i].r)t[++top]=d[i],mx=d[i].r; n=top;up(i,1,n)d[i]=t[i]; m=min(m,n); ll l=-1e18,r=1e18; while(l+1<r){ ll mid=l+r>>1; if(chk(mid))r=mid; else l=mid; } chk(r); cout<<(long long)(res.sum+m*r); } int main(){ //freopen("minion.in","r",stdin),freopen("minion.out","w",stdout); slv(); return 0; }