#include <bits/stdc++.h>
using namespace std;
const long long inf = 1ll << 60;
class solver {
public:
multiset<int> already, candidate;
long long ans;
int m;
solver(int m): m(m) {
ans = 0;
}
void insert(int x) {
if ((int) already.size() == m) {
if (x > *already.begin()) {
ans += x - *already.begin();
candidate.insert(*already.begin());
already.erase(already.begin());
already.insert(x);
} else {
candidate.insert(x);
}
} else {
already.insert(x);
ans += x;
}
}
void erase(int x) {
if (candidate.find(x) != candidate.end()) {
candidate.erase(candidate.find(x));
} else {
already.erase(already.find(x));
ans -= x;
if (!candidate.empty()) {
ans += *candidate.rbegin();
already.insert(*candidate.rbegin());
candidate.erase(--candidate.end());
}
}
}
long long query() {
return ans;
}
};
int main() {
#ifdef wxh010910
freopen("input.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i].second >> a[i].first;
}
sort(a.begin(), a.end());
int l = 0, r = -1;
long long ans = -inf;
solver s(m);
auto get = [&](int ll, int rr) {
while (r < rr) {
s.insert(a[++r].second);
}
while (l > ll) {
s.insert(a[--l].second);
}
while (r > rr) {
s.erase(a[r--].second);
}
while (l < ll) {
s.erase(a[l++].second);
}
return s.query() - 2 * (a[rr].first - a[ll].first);
};
function<void(int, int, int, int)> solve = [&](int l, int r, int ll, int rr) {
if (l > r) {
return;
}
int mid = (l + r) >> 1;
long long res = -inf;
int pos = -1;
for (int i = ll; i <= mid - m + 1 && i <= rr; ++i) {
long long weight = get(i, mid);
if (res < weight) {
res = weight;
pos = i;
}
}
ans = max(ans, res);
solve(l, mid - 1, ll, pos);
solve(mid + 1, r, pos, rr);
};
solve(m - 1, n - 1, 0, n - m);
cout << ans << "\n";
return 0;
}
