#include <bits/stdc++.h>
using namespace std;
struct ab {
int a, b;
};
struct event {
int type, val, t;
};
int m;
const int MAX_N = 2e5;
const long long INF = 1e18;
const int MAX_EVENTS = 1e6;
ab v[MAX_N + 1];
int timee = 0;
long long sumA;
event events[MAX_EVENTS];
int nrEv = 0;
multiset <int> s;
long long solve( int ll, int lr, int rl, int rr ) {
if ( ll > lr || rl > rr )
return -INF;
int l = (ll + lr) / 2;
long long answer = -INF;
int bestR = rr;
int t = timee;
for ( int i = l; i <= lr && i < rl; i++ ) {
s.insert( v[i].a );
sumA += v[i].a;
events[nrEv++] = { 1, v[i].a, ++timee };
if ( s.size() > m ) {
sumA -= *s.begin();
events[nrEv++] = { -1, *s.begin(), ++timee };
s.erase( s.begin() );
}
}
for ( int r = max( l, rl ); r <= rr; r++ ) {
s.insert( v[r].a );
sumA += v[r].a;
events[nrEv++] = { 1, v[r].a, ++timee };
if ( s.size() > m ) {
sumA -= *s.begin();
events[nrEv++] = { -1, *s.begin(), ++timee };
s.erase( s.begin() );
}
if ( s.size() >= m ) {
if ( sumA - 2 * (v[r].b - v[l].b) > answer ) {
answer = sumA - 2 * (v[r].b - v[l].b);
bestR = r;
}
}
}
while ( nrEv > 0 && events[nrEv - 1].t > t ) {
int x = events[nrEv - 1].val;
if ( events[nrEv - 1].type == 1 ) {
s.erase( s.find( x ) );
sumA -= x;
} else {
s.insert( x );
sumA += x;
}
nrEv--;
}
for ( int i = min( rl - 1, lr ); i >= l; i-- ) {
s.insert( v[i].a );
sumA += v[i].a;
events[nrEv++] = { 1, v[i].a, ++timee };
if ( s.size() > m ) {
sumA -= *s.begin();
events[nrEv++] = { -1, *s.begin(), ++timee };
s.erase( s.begin() );
}
}
answer = max( answer, solve( ll, l - 1, rl, bestR ) );
while ( nrEv > 0 && events[nrEv - 1].t > t ) {
int x = events[nrEv - 1].val;
if ( events[nrEv - 1].type == 1 ) {
s.erase( s.find( x ) );
sumA -= x;
} else {
s.insert( x );
sumA += x;
}
nrEv--;
}
for ( int i = max( rl, lr + 1 ); i < bestR; i++ ) {
s.insert( v[i].a );
sumA += v[i].a;
events[nrEv++] = { 1, v[i].a, ++timee };
if ( s.size() > m ) {
sumA -= *s.begin();
events[nrEv++] = { -1, *s.begin(), ++timee };
s.erase( s.begin() );
}
}
answer = max( answer, solve( l + 1, lr, bestR, rr ) );
while ( nrEv > 0 && events[nrEv - 1].t > t ) {
int x = events[nrEv - 1].val;
if ( events[nrEv - 1].type == 1 ) {
s.erase( s.find( x ) );
sumA -= x;
} else {
s.insert( x );
sumA += x;
}
nrEv--;
}
return answer;
}
int main() {
int n;
cin.tie( NULL );
ios_base::sync_with_stdio( false );
cin >> n >> m;
for ( int i = 1; i <= n; i++ )
cin >> v[i].a >> v[i].b;
sort( v + 1, v + 1 + n, []( ab x, ab y ) {
return x.b < y.b;
} );
cout << solve( 1, n, 1, n );
return 0;
}
