#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
const int MXN = 200005, LG = 35, MXC = 1000000005;
int n, m;
pii p[MXN];
int ans;
namespace PSMG {
#define mid ((l + r) >> 1)
int val[MXN * LG], cnt[MXN * LG], L[MXN * LG], R[MXN * LG], nc;
vector<int> rt;
int new_node(int ref) {
val[nc] = val[ref];
cnt[nc] = cnt[ref];
L[nc] = L[ref];
R[nc] = R[ref];
return nc++;
}
int modify(int id, int l, int r, int p, int v) {
id = new_node(id);
if (l + 1 == r) {
val[id] += p * v;
cnt[id] += v;
return id;
}
if (p < mid) L[id] = modify(L[id], l, mid, p, v);
else R[id] = modify(R[id], mid, r, p, v);
val[id] = val[L[id]] + val[R[id]];
cnt[id] = cnt[L[id]] + cnt[R[id]];
return id;
}
void init() {
nc = 2;
rt.push_back(1);
FOR(i, 0, n) {
rt.push_back(modify(rt.back(), 0, MXC, p[i].sc, 1));
}
}
int query(int idl, int idr, int l, int r, int bnd) {
// debug(l, r, bnd, cnt[idl], cnt[idr]);
if (bnd == cnt[idr] - cnt[idl]) {
// debug(val[idl], val[idr]);
return val[idr] - val[idl];
}
int rcnt = cnt[R[idr]] - cnt[R[idl]];
if (rcnt >= bnd) return query(R[idl], R[idr], mid, r, bnd);
return val[R[idr]] - val[R[idl]] + query(L[idl], L[idr], l, mid, bnd - rcnt);
}
int calc(int l, int r) {
// debug(l, r);
return query(rt[l], rt[r], 0, MXC, m - 2);
}
#undef mid
}
pii calc(int id, int l, int r) {
pii ans = mp(0LL, -1LL);
FOR(i, l, r + 1) {
if (id - i + 1 < m) continue;
ans = max(ans, mp(PSMG::calc(i + 1, id) + p[id].sc - 2 * p[id].fs + p[i].sc + 2 * p[i].fs, i));
// debug(i + 1, id, ans.fs);
}
return ans;
}
void solve(int l, int r, int kl, int kr) {
if (l == r) return;
// debug(l, r, kl, kr);
int mid = (l + r) >> 1;
auto [val, k] = calc(mid, kl, kr);
// debug(mid, val, k);
ans = max(ans, val);
solve(l, mid, kl, k);
solve(mid + 1, r, k, kr);
}
void miku() {
cin >> n >> m;
FOR(i, 0, n) cin >> p[i].sc >> p[i].fs;
sort(p, p + n);
PSMG::init();
// solve(0, n, 0, n);
FOR(i, 0, n) FOR(j, i + m, n + 1) {
ans = max(ans, p[i].sc + p[i].fs * 2 + p[j - 1].sc - p[j - 1].fs * 2 + PSMG::calc(i + 1, j - 1));
}
cout << ans << '\n';
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit);
miku();
return 0;
}
