#include<bits/stdc++.h>
using namespace std;
#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define fi first
#define se second
#define ll long long
#define eb emplace_back
#define pb push_back
#define __builtin_popcount __builtin_popcountll
#define _ << " " <<
template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}
const int N=202020;
int n,m; ll res=-1e18;
ii cake[N];
struct Node{
Node *lc,*rc;
ll sum; int cnt;
Node(){
lc=rc=nullptr;
sum=0; cnt=0;
}
};
Node *ver[N];
ll walk(int ql, int qr){
Node *idL=ver[ql-1],*idR=ver[qr];
int l=1, r=1e9; ll res=0; int lt=m;
while(l<r){
int mid=(l+r)>>1;
int cntR=0; ll sumR=0;
if(idR!=0 && idR->rc!=0){
cntR+=idR->rc->cnt;
sumR+=idR->rc->sum;
}
if(idL!=0 && idL->rc!=0){
cntR-=idL->rc->cnt;
sumR-=idL->rc->sum;
}
// cout<<l _ mid _ r _ lt _ cntR _ sumR<<'\n';
if(lt>cntR){
lt-=cntR;
res+=sumR;
if(idR!=0) idR=idR->lc;
if(idL!=0) idL=idL->lc;
r=mid;
} else{
if(idR!=0) idR=idR->rc;
if(idL!=0) idL=idL->rc;
l=mid+1;
}
}
// cout<<res _ lt _ l<<'\n';
return res+1LL*lt*l;
}
ll cost(int i, int j){
if(j-i+1<m) return -1e18;
// cerr<<i _ j _ walk(i,j)<<'\n';
return walk(i,j)-2*(cake[j].se-cake[i].se);
}
void calc(int L, int R, int optL, int optR){
if(L>R) return;
int M=(L+R)>>1;
ll pos=0, ans=-1e18;
foru(opt,optL,min(optR,M)){
if(maxi(ans,cost(opt,M))){
pos=opt;
}
}
maxi(res,ans);
calc(L,M-1,optL,pos);
calc(M+1,R,pos,optR);
}
Node *update(int x, Node *old, int l, int r){
if(l==r){
Node *cur=new Node();
*cur=*old;
cur->cnt++;
cur->sum+=x;
return cur;
}
Node *cur=new Node();
int mid=(l+r)>>1;
if(x<=mid){
if(old->lc==0) old->lc=new Node();
cur->lc=update(x,old->lc,l,mid);
cur->rc=old->rc;
} else{
cur->lc=old->lc;
if(old->rc==0) old->rc=new Node();
cur->rc=update(x,old->rc,mid+1,r);
}
if(cur->lc!=0){
cur->sum+=cur->lc->sum;
cur->cnt+=cur->lc->cnt;
}
if(cur->rc!=0){
cur->sum+=cur->rc->sum;
cur->cnt+=cur->rc->cnt;
}
return cur;
}
void solve(){
cin>>n>>m;
foru(i,1,n) cin>>cake[i].fi>>cake[i].se;
sort(cake+1, cake+1+n, [](ii x, ii y){return x.se<y.se;});
// foru(i,1,n) cout<<cake[i].fi<<'\n';
ver[0]=new Node();
foru(i,1,n){
ver[i]=update(cake[i].fi,ver[i-1],1,1e9);
}
// cout<<walk(1,5)<<'\n';
calc(m,n,1,n);
cout<<res<<'\n';
}
int32_t main(){
#define task "test"
if(fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin.tie(0)->sync_with_stdio(0);
int tc=1; //cin>>tc;
foru(i,1,tc){
solve();
}
}
