#include<bits/stdc++.h>
#define ll long long
#define int long long
const int nmax = 2e5 + 5, N = 1e5;
const ll oo = 1e18 + 1, base = 311;
const int lg = 15, M = 10;
const ll mod = 998244353, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;
int n, m;
pii a[nmax];
ll best[nmax];
multiset<pii> one, two;
struct node{
int l, r, from, to;
};
vector<node> adj[50];
ll pre[nmax], suf[nmax];
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n >> m;
for(int i = 1; i <= n; ++i) cin >> a[i].fi >> a[i].se;
sort(a + 1, a + 1 + n, [](pii a, pii b){
return a.se < b.se;
});
pre[0] = suf[n + 1] = -oo;
for(int i = 1; i <= n; ++i){
pre[i] = max(pre[i - 1], a[i].fi + 2 * a[i].se);
}
// cout << pre[1] << ' ';
for(int i = n; i >= 1; --i){
suf[i] = max(suf[i + 1], a[i].fi - 2 * a[i].se);
}
adj[1].push_back({1, n, 1, n});
ll ans = -oo;
for(int e = 1; e <= 20; ++e){
if(adj[e].empty()) continue;
int pos = 1;
ll cur = 0;
// cout << endl;
one.clear();two.clear();
for(auto [l, r, from, to] : adj[e]){
int mid = r + l >> 1;
auto &p = best[mid];
p = from;
int ma = -oo;
for(int i = max(mid, from); i <= to; ++i){
if(i - mid + 1 < m) continue;
while(pos < i){
one.insert({a[pos].fi, pos});
two.insert({pos, a[pos].fi});
cur += a[pos].fi;
++pos;
}
while(two.size()){
auto it = two.begin();
pii tx = *it;
if(tx.fi <= mid){
cur -= tx.se;
one.erase({tx.se, tx.fi});
two.erase(it);
}
else break;
}
while(one.size() > m - 2){
auto it = one.begin();
pii tx = *it;
cur -= tx.fi;
two.erase({tx.se, tx.fi});
one.erase(it);
}
// if(mid == 1 && i == 3) cout << mid << ' ' << pre[mid] << ' ' << suf[i] << endl;
if(ma < pre[mid] + suf[i] + cur){
ma = pre[mid] + suf[i] + cur;
p = i;
ans = max(ans, ma);
}
}
if(l < mid) adj[e + 1].push_back({l, mid - 1, from, p});
if(mid < r) adj[e + 1].push_back({mid + 1, r, p, to});
}
}
cout << ans;
}
/*
5 4
1 2
2 3
3 4
3 5
1 2 1 3 4
*/
