#include <bits/stdc++.h>
#define ar array
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int maxn = 2e5 + 5;
vector<int> comp;
struct node {
int cnt = 0;
ll sum = 0;
node *l, *r;
node(int c=0, ll v=0) : cnt(c), sum(v), l(nullptr), r(nullptr) {}
node(node *l, node *r) : l(l), r(r) {
if(l) sum += l->sum, cnt += l->cnt;
if(r) sum += r->sum, cnt += r->cnt;
}
};
node *build(int l, int r) {
if(l == r) return new node(0, 0);
int tm = (l + r) / 2;
return new node(build(l, tm), build(tm+1, r));
}
node *update(node *u, int tl, int tr, int p) {
if(tl == tr) return new node(u->cnt + 1, u->sum + comp[p]);
int tm = (tl + tr) / 2;
if(p <= tm) return new node(update(u->l, tl, tm, p), u->r);
return new node(u->l, update(u->r, tm+1, tr, p));
}
int n, m;
vector<ar<int, 2> > a(maxn);
vector<node*> R;
ll find(node *u, node *v, int tl, int tr, int k) {
if(tl == tr) return 1ll * k * comp[tl];
int tm = (tl + tr) / 2;
if(u->r->cnt - v->r->cnt >= k) return find(u->r, v->r, tm+1, tr, k);
return u->r->sum - v->r->sum + find(u->l, v->l, tl, tm, k - (u->r->cnt - v->r->cnt));
}
ll query(int l, int r, int k) {
return find(R[r], R[l-1], 1, n, k);
}
signed main() {
ios_base::sync_with_stdio(false);
cout.tie(0); cin.tie(0);
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> a[i][1] >> a[i][0];
sort(a.begin()+1, a.begin()+n+1);
set<int> st; st.insert(-1);
for(int i=1; i<=n; i++) st.insert(a[i][1]);
comp = vector<int>(st.begin(), st.end());
R.push_back(build(1, n));
for(int i=1; i<=n; i++) {
int p = lower_bound(comp.begin(), comp.end(), a[i][1]) - comp.begin();
R.push_back(update(R[i-1], 1, n, p));
}
ll ans = -1e18;
for(int i=1; i<=n; i++)
for(int j=i+m-1; j<=n; j++)
ans = max(ans, a[i][1] + a[j][1] + 2ll * (a[i][0] - a[j][0]) + query(i+1, j-1, m-2));
cout << ans << '\n';
}
