#include <bits/stdc++.h>
#define fr first
#define sc second
#define ll long long
#define ok puts("ok");
using namespace std;
const int N = (int)2e5 + 7;
pair < ll, ll > ar[N];
int n, m;
ll pref[N], suf[N];
ll ans;
int siz = 1;
int root[N];
struct node {
int l, r;
ll sum;
int cnt;
node() {
l = r = 0;
sum = 0;
cnt = 0;
}
};
node tree[N * 100];
void build(int v = 1, int l = 1, int r = n) {
if (l == r) {
return ;
}
int mid = (l + r) >> 1;
tree[v].l = ++siz;
tree[v].r = ++siz;
build(tree[v].l, l, mid);
build(tree[v].r, mid + 1, r);
}
void upd(int ov, int nv, int pos, int val, int l = 1, int r = n) {
if (l == r) {
tree[nv].sum += val;
tree[nv].cnt++;
return ;
}
int mid = (l + r) >> 1;
if (pos <= mid) {
tree[nv].l = ++siz;
tree[nv].r = tree[ov].r;
upd(tree[ov].l, tree[nv].l, pos, val, l, mid);
} else {
tree[nv].l = tree[ov].l;
tree[nv].r = ++siz;
upd(tree[ov].r, tree[nv].r, pos, val, mid + 1, r);
}
tree[nv].sum = tree[tree[nv].l].sum + tree[tree[nv].r].sum;
tree[nv].cnt = tree[tree[nv].l].cnt + tree[tree[nv].r].cnt;
}
ll getsum(int lv, int rv, int l = 1, int r = n, int keep = m - 2) {
if (keep == 0) return 0;
if (l == r) {
if (tree[rv].cnt - tree[lv].cnt == 0) return 0;
return (tree[rv].sum - tree[lv].sum) / (tree[rv].cnt - tree[lv].cnt) * keep;
}
ll res = 0;
int mid = (l + r) >> 1;
if (tree[tree[rv].r].cnt - tree[tree[lv].r].cnt <= keep) {
res = tree[tree[rv].r].sum - tree[tree[lv].r].sum;
return res + getsum(tree[lv].l, tree[rv].l, l, mid, keep - (tree[tree[rv].r].cnt - tree[tree[lv].r].cnt));
} else {
return getsum(tree[lv].r, tree[rv].r, mid + 1, r, keep);
}
}
ll get(ll l, ll r) {
return getsum(root[l - 1], root[r]);
}
void make(int l, int r, int optl, int optr) {
if (l > r) return ;
int mid = (l + r) >> 1;
int opt = min(mid + m - 1, optr);
ll res = -1e18;
for (int i = max(mid + m - 1, optl); i <= optr; i++) {
ll cost = get(mid + 1, i - 1) + pref[mid] + suf[i];
if (cost > res) {
res = cost;
opt = i;
}
}
// cout << mid << ' ' << res << ' ' << opt << endl;
if (res > ans) {
ans = res;
}
make(l, mid - 1, optl, opt);
make(mid + 1, r, opt, optr);
}
void solve() {
build();
root[0] = 1;
vector < int > vx;
int asd[N];
for (int i = 1; i <= n; i++) {
vx.push_back(ar[i].fr);
}
sort(vx.begin(), vx.end());
vx.resize(unique(vx.begin(), vx.end()) - vx.begin());
for (int i = 1; i <= n; i++) {
asd[i] = lower_bound(vx.begin(), vx.end(), ar[i].fr) - vx.begin() + 1;
}
for (int i = 1; i <= n; i++) {
root[i] = ++siz;
upd(root[i - 1], root[i], asd[i], ar[i].fr);
}
make(1, n, 1, n);
}
main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%lld %lld", &ar[i].sc, &ar[i].fr);
}
sort(ar + 1, ar + n + 1);
pref[0] = -1e18;
for (int i = 1; i <= n; i++) {
swap(ar[i].fr, ar[i].sc);
pref[i] = max(pref[i - 1], ar[i].fr + 2 * ar[i].sc);
}
suf[n + 1] = -1e18;
for (int i = n; i >= 1; i--) {
suf[i] = max(suf[i + 1], ar[i].fr - 2 * ar[i].sc);
}
ans = -1e18;
if (m == 3) {
for (int i = 2; i < n; i++) {
ans = max(ans, pref[i - 1] + suf[i + 1] + ar[i].fr);
}
} else {
solve();
}
cout << ans;
}
