#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll INF = 1e18;
vector<ll> v0,c0;
vector<ll> imax,ans;
ll N,M;
ll cval = 0;
multiset<ll> shigh,slow;
ll ca,cb;
void iset() { //initialize to [0,M-1]
ca = 0;
cb = M-1;
for (ll i=0;i<M;i++) {
shigh.insert(v0[i]);
cval += v0[i];
}
}
void renorm() {
if (shigh.size()==0 || slow.size()==0) {
return;
}
auto A0 = shigh.begin();
ll x0 = *A0;
auto A1 = --slow.end();
ll x1 = *A1;
if (x1>x0) {
shigh.erase(A0);
slow.erase(A1);
cval += (x1-x0);
shigh.insert(x1);
slow.insert(x0);
renorm();
}
}
void move(ll a, ll b) {
while (b>cb) {
slow.insert(v0[cb+1]);
cb++;
}
while (a<ca) {
slow.insert(v0[ca-1]);
ca--;
}
//now contract
while (b<cb) {
if (slow.find(v0[cb])!=slow.end()) {
slow.erase(slow.find(v0[cb]));
cb--;
} else {
//erase from shigh, then pop highest from slow and insert
auto A0 = --slow.end();
ll x0 = *A0; slow.erase(A0);
auto A1 = shigh.find(v0[cb]);
assert(A1!=shigh.end());
shigh.erase(A1);
shigh.insert(x0);
cval += -v0[cb]+x0;
cb--;
}
}
while (a>ca) {
if (slow.find(v0[ca])!=slow.end()) {
slow.erase(slow.find(v0[ca]));
ca++;
} else {
//erase from shigh, then pop highest from slow and insert
auto A0 = --slow.end();
ll x0 = *A0; slow.erase(A0);
auto A1 = shigh.find(v0[ca]);
assert(A1!=shigh.end());
shigh.erase(A1);
shigh.insert(x0);
cval += -v0[ca]+x0;
ca++;
}
}
renorm();
}
void solve(ll xmin, ll xmax, ll ymin, ll ymax) {
if (xmin>xmax) {
return;
}
ymin = max(ymin,xmin+M-1);
assert(ymax>=ymin);
ll xq = (xmin+xmax)/2;
ll ym1 = max(ymin,xq+M-1);
for (ll y=ym1;y<=ymax;y++) {
move(xq,y);
ll cval1 = cval-2*c0[y]+2*c0[xq];
if (cval1>=ans[xq]) {
ans[xq]=cval1;
imax[xq]=y;
}
}
solve(xmin,xq-1,ymin,imax[xq]);
solve(xq+1,xmax,imax[xq],ymax);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> N >> M;
vector<pii> cv0;
for (ll i=0;i<N;i++) {
ll v1,c1; cin >> v1 >> c1;
cv0.push_back({c1,v1});
}
sort(cv0.begin(),cv0.end());
for (ll i=0;i<N;i++) {
v0.push_back(cv0[i].second);
c0.push_back(cv0[i].first);
}
iset();
imax = vector<ll>(N-M+1,-1);
ans = vector<ll>(N-M+1,-INF);
solve(0,N-M,M-1,N-1);
ll ansf = -INF;
for (ll x: ans) {
ansf = max(ansf,x);
}
cout << ansf << "\n";
}
