#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const int N = 2e5+10;
const ll INF = 1e18;
struct Vertex {
Vertex *l, *r;
pii val;
Vertex(pii x) : l(nullptr), r(nullptr), val(x) {}
Vertex(Vertex *l, Vertex *r) : l(l), r(r), val({0, 0}) {
if (l) val.first+=l->val.first, val.second+=l->val.second;
if (r) val.first+=r->val.first, val.second+=r->val.second;
}
};
Vertex* build(int l, int r) {
if (l == r) return new Vertex(make_pair(0, 0));
int m=(l+r)/2;
return new Vertex(build(l, m), build(m+1, r));
}
Vertex* upd(Vertex* v, int l, int r, int p, ll nvl) {
if (l == r) {
return new Vertex(make_pair(v->val.first+nvl, v->val.second+1));
} int m=(l+r)/2;
if (p <= m) return new Vertex(upd(v->l, l, m, p, nvl), v->r);
return new Vertex(v->l, upd(v->r, m+1, r, p, nvl));
}
ll que(Vertex* vl, Vertex *vr, int l, int r, int x) {
if (l == r) {
ll k=vr->val.second-vl->val.second, sm=vr->val.first-vl->val.first;
assert(k >= x);
return (sm/k)*x;
}
int m=(l+r)/2, rcnt=vr->r->val.second-vl->r->val.second;
if (rcnt >= x) return que(vl->r, vr->r, m+1, r, x);
return que(vl->l, vr->l, l, m, x-rcnt)+(vr->r->val.first-vl->r->val.first);
}
ll n, m, dp[N];
vector<pii> x;
set<int> st;
map<int, int> sc;
pii mx(pii a, pii b) {
if (a.first > b.first) return a;
if (b.first > a.first) return b;
if (a.first == b.first) {
if (a.second < b.second) return a;
return b;
}
}
vector<Vertex*> rts;
void solve(int l, int r, int opl, int opr) {
if (l > r) return;
int md=(l+r)/2;
pii tmp={-INF, n};
for (int i=max(1ll*opl, md+m-1); i<=opr; ++i) {
assert(i-md+1 >= m);
ll q=que(rts[md], rts[i-1], 1, n, m-2);
tmp=mx(tmp, {q+x[i-1].second+x[md-1].second-2*abs(x[i-1].first-x[md-1].first), i});
} dp[md]=tmp.first;
solve(l, md-1, opl, tmp.second), solve(md+1, r, tmp.second, opr);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for (int i=1; i<=n; ++i) {
ll v, c; cin>>v>>c;
x.push_back({c, v}); st.insert(v);
} sort(x.begin(), x.end());
int i=1;
for (auto u : st) sc[u]=i++;
rts.push_back(build(1, n));
for (int i=1; i<=n; ++i) {
rts.push_back(upd(rts.back(), 1, n, sc[x[i-1].second], x[i-1].second));
}
solve(1, n-m+1, 1, n);
ll ans=-INF;
for (int i=1; i<=n-m+1; ++i) ans=max(ans, dp[i]);
cout<<ans<<"\n";
}
