#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define f first
#define s second
#define ub(x,y) upper_bound(all(y),x)-y.begin()
using namespace std;
const int mxn=2e5+5;
struct node{
ll a,b;
node*l,*r;
node (int a,ll b):a(a),b(b),l(NULL),r(NULL){};
node (node *l,node *r):a(l->a+r->a),b(l->b+r->b),l(l),r(r){};
}*rt[mxn];
int N,M,sz;
ll v[mxn],c[mxn];
vector<ll>g;
node* build(int l,int r){
if(l==r)return new node(0,0);
int m=(l+r)>>1;
return new node(build(l,m),build(m+1,r));
}
node *upd(node*t,int l,int r,int idx,ll v){
if(l==r)return new node(t->a+1,t->b+v);
int m=(l+r)>>1;
if(m>=idx)return new node(upd(t->l,l,m,idx,v),t->r);
else return new node(t->l,upd(t->r,m+1,r,idx,v));
}ll ans=-1e16;
ll qr(node *tl,node *tr,int l,int r,int k){
if(l==r){
return min(tr->b-tl->b,1ll*k*g[l-1]);
}int m=(l+r)>>1;int idx=tr->r->a-tl->r->a;
if(idx>=k)return qr(tl->r,tr->r,m+1,r,k);
else return tr->r->b-tl->r->b+qr(tl->l,tr->l,l,m,k-idx);
}
void solve(int l,int r,int opl,int opr){
if(r<l)return;
int m=(l+r)>>1;
pair<ll,ll>t={-1e16,0};
for(int i=opl;i<=min(opr,m-1);i++){
if(m-i+1<M)break;
ll rs=-2*c[m]+2*c[i]+qr(rt[i],rt[m-1],1,sz,M-2)+v[m]+v[i];
t=max(t,{rs,i});
}ans=max(ans,t.f);
if(t.s==0)solve(l,m-1,opl,opr);
else solve(l,m-1,opl,t.s);
if(t.s==0)solve(m+1,r,opl,opr);
else solve(m+1,r,t.s,opr);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>N>>M;vector<pair<ll,ll>>tmp;
for(int i=0;i<N;i++){
int x,y;cin>>x>>y;
tmp.pb({y,x});g.pb(x);
}sort(all(tmp));sort(all(g));g.erase(unique(all(g)),g.end());
for(int i=0;i<N;i++)v[i+1]=tmp[i].s,c[i+1]=tmp[i].f;sz=g.size();
rt[0]=build(1,sz);
for(int i=1;i<=N;i++)rt[i]=upd(rt[i-1],1,sz,ub(v[i],g),v[i]);
solve(1,N,1,N);cout<<ans;
}
