#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 42, INF = 1e18 + 42;
struct Perl {
int c, t;
};
Perl perl[N];
multiset<int> best, other;
int n, m, ans = -INF, deb = -1, fin = -1, sum = 0;
inline void add(int val) {
sum += val;
best.insert(val);
if((int)best.size() == m-1) {
sum -= *best.begin();
other.insert(*best.begin());
best.erase(best.begin());
}
}
inline void del(int val) {
auto it = other.find(val);
if(it == other.end()) {
sum -= val;
it = best.find(val);
best.erase(it);
it = other.end();
it--;
sum += *it;
best.insert(*it);
other.erase(it);
} else {
other.erase(it);
}
}
void dpr(int l, int r, int lOpt, int rOpt) {
if(l == r) return;
int i = ((l + r) >> 1),
left = min(lOpt, i-m+1),
right = min(rOpt, i-m+1);
if(deb == -1) deb = fin = i;
while(deb-1 > right) add(perl[--deb].c);
while(fin+1 <= i) add(perl[fin++].c);
while(deb <= right) del(perl[deb++].c);
while(fin > i) del(perl[--fin].c);
int val = sum + perl[right].c + 2 * perl[right].t, opt = right;
for(int j = right-1; j >= left; j--) {
add(perl[--deb].c);
int x = sum + perl[j].c + 2 * perl[j].t;
if(x > val) {
val = x;
opt = j;
}
}
ans = max(ans, val + perl[i].c - 2 * perl[i].t);
dpr(l, i, lOpt, opt);
dpr(i+1, r, opt, rOpt);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> perl[i].c >> perl[i].t;
sort(perl, perl + n,
[](Perl a, Perl b) {
return a.t < b.t;
});
dpr(m-1, n, 0, n-m);
cout << ans << '\n';
}
