#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5, maxN = 8e5 + 5, inf = 1e9+5, INF = 1e18;
int n, m;
pair<int,int> a[maxn];
vector<int> L[maxN], R[maxN];
int ans = -INF;
void dnc(int id, int l, int r) {
int sz = min(r - l + 1, m);
if (l == r) {
L[id] = {-a[l].first * 2, a[l].second - a[l].first * 2};
R[id] = {a[l].first * 2, a[l].second + a[l].first * 2};
// cout << l << " " << r << endl;
// cout << L[id][0] << " " << L[id][1] << endl;
// cout << R[id][0] << " " << R[id][1] << endl;
return;
}
int mid = (l+r)/2;
dnc(id*2, l, mid); dnc(id*2+1, mid+1, r);
int lsz = L[id*2].size() - 1, rsz = L[id*2+1].size() - 1;
for (int i=0;i<=m;i++) {
if (i <= lsz && m-i <= rsz) ans = max(R[id*2][i] + L[id*2+1][m-i], ans);
// if (i <= lsz && m-i <= rsz) cout << "wtf " << l << " " << r << " " << i << " " << R[id*2][i] << " " << L[id*2+1][m-i] << " " << R[id*2][i] + L[id*2+1][m-i] << endl;
// if (i <= lsz && m-i <= rsz) if (R[id*2][i] + L[id*2+1][m-i] == 568584951) {
// cout << id << " " << l << " " << r << " " << endl;
// cout << i << " " << R[id*2][i] << " " << L[id*2+1][m-i] << endl;
// }
}
vector<int> vec;
for (int i=l;i<=mid;i++) vec.push_back(a[i].second);
sort(vec.rbegin(), vec.rend());
while (vec.size() > sz) vec.pop_back();
reverse(vec.begin(), vec.end());
vec.push_back(0);
reverse(vec.begin(), vec.end());
int vsz = vec.size();
for (int i=1;i<vsz;i++) vec[i] += vec[i-1];
// if (sz == 2) for (int i:vec) cout << i << " "; cout << endl;
vector<pair<int,int>> pos = {{0, 0}};
for (int i=1;i<=rsz;i++) {
int ll = 0, rr = pos.size() - 1;
while (ll < rr) {
int midd = (ll+rr+1)/2;
auto [f, s] = pos[midd];
// if (l == 5 && r == 8 && i == 2) cout << ll << " " << rr << " " << midd << endl;
if (f-i < 0 || L[id*2+1][i] + vec[f-i] < L[id*2+1][s] + vec[f-s]) ll = midd;
else rr = midd-1;
}
// cout << "test\n";
auto [F, S] = pos[ll];
// if (l == 5 && r == 8) cout << "lll " << i << " " << ll << endl;
while (pos.size() > ll+1) pos.pop_back();
ll = max(pos[ll].first, i), rr = sz;
// if (l == 5 && r == 8) cout << "ll " << i << " " << ll << endl;
while (ll < rr) {
int midd = (ll+rr)/2;
if (midd-S >= vsz || (midd-i < vsz && L[id*2+1][i] + vec[midd-i] > L[id*2+1][S] + vec[midd-S])) rr = midd;
else ll = midd + 1;
}
// if (l == 5 && r == 8) cout << "ll " << i << " " << ll << endl;
if (ll - S >= vsz || (ll-i < vsz && L[id*2+1][i] + vec[ll-i] > L[id*2+1][S] + vec[ll-S])) {
if (pos.back().first == ll) pos.pop_back();
pos.push_back({ll, i});
}
}
L[id].resize(sz+1);
int pt = -1, cur;
for (int i=0;i<=sz;i++) {
while (pt+1 < pos.size() && pos[pt+1].first == i) pt++, cur = pos[pt].second;
L[id][i] = L[id*2+1][cur] + vec[i-cur];
if (i <= lsz) L[id][i] = max(L[id*2][i], L[id][i]);
}
if (l == 5 && r == 8) {
}
vec.clear();
for (int i=mid+1;i<=r;i++) vec.push_back(a[i].second);
sort(vec.rbegin(), vec.rend());
while (vec.size() > sz) vec.pop_back();
reverse(vec.begin(), vec.end());
vec.push_back(0);
reverse(vec.begin(), vec.end());
vsz = vec.size();
for (int i=1;i<vsz;i++) vec[i] += vec[i-1];
pos = {{0, 0}};
for (int i=1;i<=rsz;i++) {
int ll = 0, rr = pos.size() - 1;
while (ll < rr) {
int midd = (ll+rr+1)/2;
auto [f, s] = pos[midd];
if (f-i < 0 || R[id*2][i] + vec[f-i] < R[id*2][s] + vec[f-s]) ll = midd;
else rr = midd-1;
}
auto [F, S] = pos[ll];
while (pos.size() > ll+1) pos.pop_back();
ll = max(pos[ll].first, i), rr = sz;
while (ll < rr) {
int midd = (ll+rr)/2;
if (midd-S >= vsz || (midd-i < vsz && R[id*2][i] + vec[midd-i] > R[id*2][S] + vec[midd-S])) rr = midd;
else ll = midd + 1;
}
if (ll-S >= vsz || (ll-i < vsz && R[id*2][i] + vec[ll-i] > R[id*2][S] + vec[ll-S])) {
if (pos.back().first == ll) pos.pop_back();
pos.push_back({ll, i});
}
}
R[id].resize(sz+1);
pt = -1;
for (int i=0;i<=sz;i++) {
while (pt+1 < pos.size() && pos[pt+1].first == i) pt++, cur = pos[pt].second;
R[id][i] = R[id*2][cur] + vec[i-cur];
// if (l==1 && r==4) cout << "14 " << i << " " << cur << " " << R[id*2][cur] << " " << vec[i-cur] << " " << L[id*2+1][cur] + vec[i-cur] << endl;
if (i <= rsz) R[id][i] = max(R[id*2+1][i], R[id][i]);
}
if (sz >= 2) {
// cout << l << " " << r << endl;
// for (int i=0;i<=sz;i++) cout << L[id][i] << " "; cout << endl;
// for (int i=0;i<=sz;i++) cout << R[id][i] << " "; cout << endl;
}
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i=1;i<=n;i++) cin >> a[i].second >> a[i].first;
sort(a+1, a+n+1);
dnc(1, 1, n);
cout << ans << "\n";
}
