#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #define int long long #define ii pair<int,int> #define fir first #define sec second #define pb push_back const int maxn=2e5; int n,m; ii apa[maxn+2]; int ans=-1e18; struct seg{ int cnt,sum,l,r; seg *lf,*rg; void build(int x,int y){ l=x,r=y; if(l==r){ cnt=sum=0; return; } int mid=(l+r)/2; lf=new seg(),rg=new seg(); lf->build(l,mid),rg->build(mid+1,r); cnt=sum=0; } void update(int pos,int val,int bny){ if(l==r){ sum+=val,cnt+=bny; return; } int mid=(l+r)/2; if(mid>=pos)lf->update(pos,val,bny); else rg->update(pos,val,bny); sum=lf->sum+rg->sum; cnt=lf->cnt+rg->cnt; } ii query(int posl,int posr){ if(l>=posl && r<=posr)return {sum,cnt}; if(l>posr || r<posl)return {0,0}; ii b=rg->query(posl,posr); ii a=lf->query(posl,posr); return {a.fir+b.fir,a.sec+b.sec}; } int walk(int brp){ if(l==r)return (sum/cnt)*min(cnt,brp); if(rg->cnt>=brp){ return rg->walk(brp); } int tot=rg->sum; tot+=lf->walk(brp-rg->cnt); return tot; } }; vector<int>comp; seg cek; int pos(int val){ int idx=lower_bound(comp.begin(),comp.end(),val)-comp.begin()+1; return idx; } int posl,posr; void range(int l,int r){ while(posl>l){ posl--; int mana=pos(apa[posl].sec); cek.update(mana,apa[posl].sec,1); } while(posl<l){ int mana=pos(apa[posl].sec); cek.update(mana,-apa[posl].sec,-1); posl++; } while(posr>r){ int mana=pos(apa[posr].sec); cek.update(mana,-apa[posr].sec,-1); posr--; } while(posr<r){ posr++; int mana=pos(apa[posr].sec); cek.update(mana,apa[posr].sec,1); } } void dnc(int l,int r,int optl,int optr){ if(l>r)return; int mid=(l+r)/2; int mx=-1e18,opt=optr; for(int q=max(optl,mid+(m-1));q<=optr;q++){ range(mid+1,q-1); int brp=cek.walk(m-2)+2*apa[mid].fir-2*apa[q].fir; //cout<<apa[q].fir<<endl; brp+=apa[mid].sec+apa[q].sec; if(mx<brp){ mx=brp; opt=q; } } ans=max(ans,mx); dnc(l,mid-1,optl,opt),dnc(mid+1,r,opt,optr); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m; for(int q=1;q<=n;q++){ cin>>apa[q].sec>>apa[q].fir; } sort(apa+1,apa+n+1); for(int q=1;q<=n;q++){ comp.pb(apa[q].sec); } sort(comp.begin(),comp.end()); comp.erase(unique(comp.begin(),comp.end()),comp.end()); cek.build(1,comp.size()); posl=1,posr=0; dnc(1,n,1,n); cout<<ans<<endl; }