#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 2e5 + 5;
int n, m;
pair<int, int> a[maxn];
int ord[maxn];
long long tree[maxn << 2];
int cnt[maxn << 2];
int lim;
long long res;
int L = 1, R;
vector<int> comp;
void update(int pos, int val, int ind = 1, int l = 1, int r = lim) {
if (l == r) {
tree[ind] += val;
cnt[ind] += (val > 0 ? 1 : -1);
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) {
update(pos, val, ind << 1, l, mid);
} else {
update(pos, val, ind << 1 | 1, mid + 1, r);
}
tree[ind] = tree[ind << 1] + tree[ind << 1 | 1];
cnt[ind] = cnt[ind << 1] + cnt[ind << 1 | 1];
}
long long walk(int k, int ind = 1, int l = 1, int r = lim) {
if (l == r) {
if (!cnt[ind]) return 0;
return tree[ind] / cnt[ind] * k;
}
int mid = (l + r) >> 1;
if (k >= cnt[ind << 1 | 1]) {
return walk(k - cnt[ind << 1 | 1], ind << 1, l, mid) + tree[ind << 1 | 1];
}
return walk(k, ind << 1 | 1, mid + 1, r);
}
void upd(int id, int delta) {
update(a[id].first, comp[a[id].first - 1] * delta);
}
long long cost(int l, int r) {
while (R < r) upd(++R, 1);
while (L > l) upd(--L, 1);
while (R > r) upd(R--, -1);
while (L < l) upd(L++, -1);
upd(l, -1), upd(r, -1);
long long cc = walk(m - 2) + comp[a[r].first - 1] + comp[a[l].first - 1];
cc -= abs(a[r].second - a[l].second) * 2;
// debug(l, r, cc, walk(m - 2));
upd(l, 1), upd(r, 1);
return cc;
}
void calc(int l, int r, int optl, int optr) {
if (l > r) return;
int mid = (l + r) >> 1;
long long xx = -1e18;
int opt = optl;
for (int i = optl; i <= min(mid - m + 1, optr); ++i) {
long long cur = cost(i, mid);
if (cur > xx) {
xx = cur;
opt = i;
}
}
res = max(res, xx);
calc(l, mid - 1, optl, opt);
calc(mid + 1, r, opt, optr);
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i].first >> a[i].second;
comp.push_back(a[i].first);
}
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
sort(a + 1, a + n + 1, [](const pair<int, int> &x, const pair<int, int> &y) -> bool {
return (x.second != y.second ? x.second < y.second : x.first < y.first);
});
for (int i = 1; i <= n; ++i) {
// debug(a[i]);
a[i].first = lower_bound(comp.begin(), comp.end(), a[i].first) - comp.begin() + 1;
}
lim = (int)comp.size();
res = -1e18;
calc(m, n, 1, n - m + 1);
cout << res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
