#include <bits/stdc++.h>
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 4e18;
const int OO = 0;
const int OOO = 1;
using namespace std;
struct order {
int m, newtime;
ll sum;
set<pair<int, int>> s;
set<pair<int, int>>::iterator it;
int stores;
order() {}
order(int M) {
m = M;
newtime = 0;
sum = -1;
s.insert({ -1, newtime++ });
it = s.begin();
stores = 1;
}
void fix() {
while (stores < m) {
if (it == s.begin()) break;
--it;
++stores;
sum += it->first;
}
while (stores > m) {
if (next(it) == s.end()) break;
--stores;
sum -= it->first;
++it;
}
}
void insert(int x) {
s.insert({ x, newtime++ });
if (it->first <= x) {
stores++;
sum += x;
}
}
void erase(int x) {
auto rit = s.lower_bound({ x, -1 });
if (rit == it) {
sum -= x;
--it;
sum += it->first;
s.erase(rit);
return;
}
if (x > it->first) {
sum -= x;
--stores;
s.erase(rit);
return;
}
s.erase(rit);
}
ll query() {
fix();
return sum;
}
};
int n, m;
vector<pair<int, int>> a;
int L = 0, R = -1;
order S;
ll query(int l, int r) {
if (r - l + 1 < m) return -inf;
while (R < r)
S.insert(a[++R].first);
while (L < l)
S.erase(a[L++].first);
while (l < L)
S.insert(a[--L].first);
while (r < R)
S.erase(a[R--].first);
return S.query();
}
ll calc(int st, int en, int optl, int optr) {
en = min(en, optr - m + 1);
if (st > en) return -inf;
if (OO) {
cout << "at calc(" << st << ", " << en << ", " << optl << ", " << optr << ")\n";
}
int mid = (st + en) / 2;
int at = -1;
ll mx = -inf;
for (int i = max(mid, optl); i <= optr; i++) {
ll res = query(mid, i) - 2 * (a[i].second - a[mid].second);
if (mx < res) {
mx = res;
at = i;
}
}
if (OO) {
cout << "the best for " << mid << " is " << at << ", with worth " << mx << '\n';
}
mx = max(mx, calc(st, mid - 1, optl, at));
mx = max(mx, calc(mid + 1, en, at, optr));
return mx;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
a.resize(n);
S = order(m);
for (auto &i : a) cin >> i.first >> i.second;
sort(a.begin(), a.end(), [](const pair<int, int> &aa, const pair<int, int> &bb) {
return aa.second < bb.second;
});
cout << calc(0, n - 1, 0, n - 1) << '\n';
}
