#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define task "text"
#define int long long
const int N = 200001;
int n;
int v[N],c[N];
vector<ll> merg(vector<ll> a,vector<ll> b,int i1=0,int i2=0){
vector<ll> r;
r.push_back(0LL);
if(i1 == 1 && i2 == 1){
r.push_back(-9e17);
r.push_back(a[i1]+b[i2]);
}else{
if(i1 == 1){
r.push_back(a[i1]+b[i2]);
}else if(i2 == 1){
r.push_back(a[i1]+b[i2]);
}
}
while(i1+1 < a.size() || i2+1 < b.size()){
int v1,v2;
if(i1+1 < a.size()) v1=a[i1+1]-a[i1];
else v1=-9e17;
if(i2+1 < b.size()) v2=b[i2+1]-b[i2];
else v2=-9e17;
if(v1 >= v2){
i1++;
r.push_back(a[i1]+b[i2]);
}else{
i2++;
r.push_back(a[i1]+b[i2]);
}
}
return r;
}
vector<ll> comb(vector<ll> a,vector<ll> b){
if(a.size() > b.size()) swap(a,b);
vector<ll> ret;
for(int i=0;i<a.size();i++){
ret.push_back(max(a[i],b[i]));
}
for(int i=a.size();i<b.size();i++){
ret.push_back(b[i]);
}
return ret;
}
vector<vector<ll>> dnc(int l,int r){
//vec[0] = ket qua
//vec[1] = chi cong o left
//vec[2] = chi tru o right
//vec[3] = sum
if(l == r){
vector<vector<ll>> ret;
vector<ll> ve;
ve.push_back(0LL);
ve.push_back(v[l]);
ret.push_back(ve);
ve.resize(1);
ve.push_back(c[l]+v[l]);
ret.push_back(ve);
ve.resize(1);
ve.push_back(v[l]-c[l]);
ret.push_back(ve);
ve.clear();
ve.push_back(0LL);
ve.push_back(v[l]);
ret.push_back(ve);
//if(l == 2) cerr<<ret.size()<<'\n';
return ret;
}
int mid=(l+r)>>1;
vector<vector<ll>> a=dnc(l,mid);
vector<vector<ll>> b=dnc(mid+1,r);
vector<vector<ll>> res;
vector<ll> v=comb(a[0],b[0]);
v=comb(v,merg(a[1],b[2],1,1));
res.push_back(v);
v.clear();
v=comb(a[1],b[1]);
//cerr<<b[3].size()<<'\n';
v=comb(v,merg(a[1],b[3],1,0));
//cerr<<a[1].size()<<' '<<r<<'\n';
res.push_back(v);
v.clear();
v=comb(a[2],b[2]);
v=comb(v,merg(a[3],b[2],0,1));
res.push_back(v);
v.clear();
v=merg(a[3],b[3],0,0);
res.push_back(v);
return res;
}
pair<int,int> arr[N];
signed main(){
ios::sync_with_stdio(false);cin.tie(nullptr);
if(fopen(task".inp","r")){
freopen(task".inp","r",stdin);
}
int m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>c[i];
for(int i=1;i<=n;i++) c[i]*=2LL;
for(int i=1;i<=n;i++){
arr[i]={c[i],v[i]};
}
sort(arr+1,arr+1+n);
for(int i=1;i<=n;i++){
c[i]=arr[i].fi;
v[i]=arr[i].se;
}
//for(int i=1;i<=n;i++) cerr<<v[i]<<' '<<c[i]<<'\n';
vector<vector<ll>> v=dnc(1,n);
cout<<v[0][m];
}
