//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
llo n,m;
llo ll[200000*30];
llo rr[200000*30];
llo tree[200000*30];
llo ll2[200000*30];
llo rr2[200000*30];
llo tree2[200000*30];
llo ind[200001];
vector<llo> rr3;
vector<llo> rr4;
llo co=0;
llo update(llo no,llo l,llo r,llo i){
llo cur=co;
co++;
ll[cur]=ll[no];
rr[cur]=rr[no];
tree[cur]=tree[no];
if(l==r){
tree[cur]+=1;
return cur;
}
else{
llo mid=(l+r)/2;
if(i<=mid){
ll[cur]=update(ll[no],l,mid,i);
}
else{
rr[cur]=update(rr[no],mid+1,r,i);
}
tree[cur]=tree[ll[cur]]+tree[rr[cur]];
return cur;
}
}
llo query(llo no,llo no2,llo l,llo r,llo k){
if(l==r){
return l;
}
else{
llo mid=(l+r)/2;
if(tree[ll[no2]]-tree[ll[no]]>=k){
return query(ll[no],ll[no2],l,mid,k);
}
else{
return query(rr[no],rr[no2],mid+1,r,k-(tree[ll[no2]]-tree[ll[no]]));
}
}
}
llo co2=0;
llo update2(llo no,llo l,llo r,llo i,llo val){
llo cur=co2;
co2++;
ll2[cur]=ll2[no];
rr2[cur]=rr2[no];
tree2[cur]=tree2[no];
if(l==r){
tree2[cur]+=val;
return cur;
}
else{
llo mid=(l+r)/2;
if(i<=mid){
ll2[cur]=update2(ll2[no],l,mid,i,val);
}
else{
rr2[cur]=update2(rr2[no],mid+1,r,i,val);
}
tree2[cur]=tree2[ll2[cur]]+tree2[rr2[cur]];
return cur;
}
}
llo query2(llo no,llo l,llo r,llo aa,llo bb){
if(r<aa or l>bb){
return 0;
}
if(aa<=l and r<=bb){
return tree2[no];
}
else{
llo mid=(l+r)/2;
return query2(ll2[no],l,mid,aa,bb)+query2(rr2[no],mid+1,r,aa,bb);
}
}
vector<pair<llo,llo>> ss;
vector<pair<llo,llo>> ee;
llo solve(llo l,llo r){
llo su=ss[l].b+ss[r].b-2*(ss[r].a-ss[l].a);
l++;
r--;
llo kk=query(rr3[l],rr3[r+1],0,n-1,m-2);
llo cot=query2(rr4[kk+1],0,n-1,l,r);//+su;
//cout<<l-1<<":"<<r+1<<":"<<cot<<endl;
//cout<<kk<<",,"<<endl;
return cot+su;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
for(llo i=0;i<2*n;i++){
ll[i]=2*i+1;
rr[i]=2*i+2;
ll2[i]=2*i+1;
rr2[i]=2*i+2;
co=max(co,rr[i]+1);
co2=max(co2,rr[i]+1);
}
for(llo i=0;i<n;i++){
llo aa,bb;
cin>>aa>>bb;
ss.pb({bb,aa});
}
sort(ss.begin(),ss.end());
/*for(auto j:ss){
cout<<j.a<<":"<<j.b<<endl;
}*/
for(llo i=0;i<n;i++){
ee.pb({-ss[i].b,i});
}
sort(ee.begin(),ee.end());
for(llo i=0;i<n;i++){
ind[ee[i].b]=i;
}
rr3.pb(0);
for(llo i=0;i<n;i++){
llo x=update(rr3.back(),0,n-1,ind[i]);
rr3.pb(x);
}
rr4.pb(0);
for(llo i=0;i<n;i++){
rr4.pb(update2(rr4.back(),0,n-1,ee[i].b,-ee[i].a));
}
llo la=-1;
llo ans=-1e18;
/* for(auto j:ss){
cout<<j.a<<"."<<j.b<<endl;
}*/
for(llo i=0;i<n;i++){
llo su=ss[i].b+2*ss[i].a;
priority_queue<llo> tt;
pair<llo,llo> ma={-1e18,-1};
for(llo j=i+1;j<n;j++){
while(tt.size()>m-2){
su+=tt.top();
tt.pop();
}
if(j>=la){
if(j-i-1>=m-2){
pair<llo,llo> cur={solve(i,j),j};
if(cur.a>ma.a){
ma=cur;
}
}
}
su+=ss[j].b;
tt.push(-ss[j].b);
}
ans=max(ans,ma.a);
la=ma.b;
}
cout<<ans<<endl;
return 0;
}
