//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <set>
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
int n, m;
pii a[maxn];
inline bool cmp(pii a, pii b) {
return a.ss < b.ss;
}
multiset<int> small, big;
ll sum = 0;
inline void add(int ind) {
sum += a[ind].ff;
big.insert(a[ind].ff);
//cout << 1 << " " << a[ind].ff << endl;
//cout << sum << endl;
if (big.size() > m) {
int ch = *big.begin();
big.erase(big.begin());
sum -= ch;
//cout << 0 << " " << ch << endl;
//cout << sum << endl;
small.insert(ch);
}
}
inline void rem(int ind) {
multiset<int>::iterator it = small.find(a[ind].ff);
if (it != small.end()) {
//cout << "erase " << *it << endl;
small.erase(it);
} else {
sum -= a[ind].ff;
//cout << "erase " << 0 << " " << a[ind].ff << endl;
big.erase(big.find(a[ind].ff));
if (big.size() < m) {
int ch = *prev(small.end());
small.erase(prev(small.end()));
sum += ch;
//cout << 1 << " " << ch << endl;
big.insert(ch);
}
}
}
int curl = 0, curr = 0;
inline void ins(int l, int r) {
while (curl > l) curl--, add(curl);
while (curr < r) add(curr), curr++;
while (curl < l) rem(curl), curl++;
while (curr > r) curr--, rem(curr);
}
ll ans = -(1LL<<60);
void solve(int l, int r, int ql, int qr) {
if (r <= l || qr <= ql) return;
if (qr - ql == 1) {
for (int i = l;i < r;i++) {
ins(ql, i + 1);
ans = max(ans, sum - 2 * (a[i].ss - a[ql].ss));
}
return;
}
int mid = (l + r) / 2;
ll best = -(1LL<<60), bind = 0;
for (int i = min(qr - 1, mid - m + 1);i >= ql;i--) {
ins(i, mid + 1);
ll val = sum - 2 * (a[mid].ss - a[i].ss);
if (val > best) {
best = val;
bind = i;
}
}
ans = max(ans, best);
solve(l, mid, ql, bind + 1);
solve(mid + 1, r, bind, qr);
}
int main() {
io
cin >> n >> m;
for (int i = 0;i < n;i++) cin >> a[i].ff >> a[i].ss;
sort(a, a + n, cmp);
for (int i = 0;i < m;i++) {
add(i);
}
curr = m;
solve(m - 1, n, 0, n);
cout << ans << "\n";
}
/*
5 3
2 1
4 2
6 4
8 8
10 16
8 4
112103441 501365808
659752417 137957977
86280801 257419447
902409188 565237611
965602301 689654312
104535476 646977261
945132881 114821749
198700181 915994879
*/
