#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int nmax = 4e6 + 5;
struct WT {
struct node {
int l, r;
vector<ll> x;
vector<ll> s;
} t[nmax];
ll lo, hi;
int build(vector<ll> seq, ll a, ll b) {
static int idx = 0;
if(seq.empty()) return -1;
int cur = idx++;
if(a == b) return cur;
int mid = (a + b) >> 1;
t[cur].x.resize(seq.size());
t[cur].s.resize(seq.size());
vector<ll> left_seq, right_seq;
for (size_t i = 0; i < seq.size(); i++) {
if(seq[i] <= mid) {
t[cur].x[i] = 0;
t[cur].s[i] = 0;
left_seq.push_back(seq[i]);
} else {
t[cur].x[i] = 1;
t[cur].s[i] = seq[i];
right_seq.push_back(seq[i]);
}
}
for (size_t i = 1; i < seq.size(); i++) {
t[cur].x[i] += t[cur].x[i-1];
t[cur].s[i] += t[cur].s[i-1];
}
t[cur].l = build(left_seq, a, mid);
t[cur].r = build(right_seq, mid+1, b);
return cur;
}
int map_left(int node, int i) {
return i - (i >= 0 ? t[node].x[i] : 0);
}
int map_right(int node, int i) {
// Số phần tử bên phải trong [0,i] là t[node].x[i]
return (i >= 0 ? t[node].x[i] : 0) - 1;
}
int countRight(int node, int l, int r) {
if(l > r || l < 0) return 0;
int res = t[node].x[r];
if(l > 0) res -= t[node].x[l-1];
return res;
}
ll sumRight(int node, int l, int r) {
if(l > r || l < 0) return 0LL;
ll res = t[node].s[r];
if(l > 0) res -= t[node].s[l-1];
return res;
}
ll getUtil(int node, ll a, ll b, int l, int r, int k) {
if(l > r || k <= 0) return 0LL;
if(a == b) {
int cnt = r - l + 1;
int take = min(cnt, k);
return (ll) take * a;
}
int mid = (a + b) >> 1;
int cntR = countRight(node, l, r);
if(cntR >= k) {
int newL = map_right(node, l);
int newR = map_right(node, r);
return getUtil(t[node].r, mid+1, b, newL, newR, k);
} else {
ll sumR = sumRight(node, l, r);
int newL = map_left(node, l);
int newR = map_left(node, r);
return sumR + getUtil(t[node].l, a, mid, newL, newR, k - cntR);
}
}
ll get(int l, int r, int k) {
if(l > r) return 0LL;
return getUtil(0, lo, hi, l, r, k);
}
} tree;
int n, m;
ll ans;
vector<array<ll, 2>> a;
int cost(int l, int r) {
return tree.get(l+1, r-1, m-2) - 2 * abs(a[l][1] - a[r][1]) + a[r][0] + a[l][0];
}
void calc(int l, int r, int opl, int opr) {
if(l > r) return;
int mid = (l + r) >> 1;
pair<ll, int> best = {-LLONG_MAX, max(0, mid - m + 1)};
if(mid - m + 1 >= 0) {
for (int k = opl; k <= min(mid - m + 1, opr); k++) {
best = max(best, { (ll) cost(k, mid), k });
}
ans = max(ans, best.first);
calc(l, mid - 1, opl, best.second);
}
calc(mid + 1, r, best.second, opr);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
a.resize(n);
for (int i = 0; i < n; i++){
cin >> a[i][0] >> a[i][1];
}
sort(a.begin(), a.end(), [](auto x, auto y) {
return x[1] < y[1];
});
vector<ll> b;
for (int i = 0; i < n; i++){
b.push_back(a[i][0]);
}
ll mn = *min_element(b.begin(), b.end());
ll mx = *max_element(b.begin(), b.end());
tree.lo = mn;
tree.hi = mx;
tree.build(b, mn, mx);
calc(0, n - 1, 0, n - 1);
cout << ans;
return 0;
}
