#include <bits/stdc++.h>
/*
Porque tú eres lo que necesito
Porque yo soy lo que tú necesitas
Que tu cuerpo es mi lugar favorito
Y tu boca mi comida favorita
Tú eres perfecta, sin el 90-60-90
Después de al mundo yo darle la vuelta
Te tenía al lado y no me había dado cuenta
Que tú eres perfecta
Quiero que exageres como yo exagero
Y no te me reías porque esto es en serio
*/
#define debug printf
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
#define ll long long
const int MAXN = 2e5+10 ;
const ll inf = 1e15 ;
using namespace std ;
struct PersistentSeg
{
vector<int> sumQtd , lef, rig ;
vector<ll> sumValues ;
PersistentSeg()
{
sumValues.resize(1,0LL) ;
sumQtd.resize(1,0) ;
lef.resize(1,0) ;
rig.resize(1,0) ;
}
int create( int pos )
{
sumValues.push_back( sumValues[pos] ) ;
sumQtd.push_back( sumQtd[pos] ) ;
lef.push_back(lef[pos] ) ;
rig.push_back(rig[pos] ) ;
return sz(lef)-1 ;
}
int mid(int l, int r ) { return (l+r)>>1 ; }
int upd(int pos, int l , int r, int x, ll val )
{
int newPos = create(pos) , aux ;
sumValues[newPos] += val ;
sumQtd[newPos]++ ;
if( l == r ) return newPos ;
if( x <= mid(l,r) )
{
aux = upd(lef[newPos], l, mid(l,r) , x , val ) ;
lef[newPos] = aux ;
}
else
{
aux = upd(rig[newPos], mid(l,r)+1, r, x, val ) ;
rig[newPos] = aux ;
}
return newPos ;
}
ll bb(int posL, int posR, int l, int r , int &m ) //returns the sum of the M bests
{
if( m <= 0 ) return 0LL ;
if( sumQtd[posR]-sumQtd[posL] <= m )
{
m -= sumQtd[posR]-sumQtd[posL] ;
return sumValues[posR]-sumValues[posL] ;
}
ll ar = bb(rig[posL], rig[posR] , mid(l,r)+1, r, m ) ;
ll al = 0LL ;
if( m ) al = bb(lef[posL], lef[posR], l , mid(l,r), m ) ;
return al + ar ;
}
} seg ;
int n , m ;
int roots[MAXN] ;
pair<int,int> pieces[MAXN] ;
vector< pair<int,int> > compression ;
ll bestAnswer = -inf ;
ll getCost(int l, int r )
{
if(r-l+1 < m ) return -inf ;
vector<ll> vec ;
ll curSum = -2LL*(pieces[r].first-pieces[l].first) + pieces[l].second + pieces[r].second ;
for(int i = l+1 ; i <= r-1 ; i++ ) vec.push_back(-pieces[i].second) ;
sort(all(vec) ) ;
for(int i = 0 ; i < m-2 ; i++ ) curSum -= vec[i] ;
return curSum ;
}
void solve(int l, int r, int optmin, int optmax )
{
if( l > r ) return ;
int mid = (l+r)>>1 ;
int opt = mid ;
ll valOpt = -inf ;
for(int i = max(optmin, mid) ; i <= optmax ; i++ )
{
ll cost = getCost(mid,i) ;
if( cost <= valOpt ) continue ;
valOpt = cost ;
opt = i ;
}
if(bestAnswer < valOpt ) bestAnswer = valOpt ;
solve(l, mid-1, optmin, opt ) ;
solve(mid+1, r, opt, optmax ) ;
}
int main()
{
scanf("%d %d", &n, &m ) ;
for(int i = 1 ; i <= n ; i++ )
scanf("%d %d", &pieces[i].second, &pieces[i].first ) ;
//I need all of them to be different for simplicity's sake
//Will this mess things up?
sort(pieces+1, pieces+1+n) ;
solve(1,n-m+1, 1, n) ;
printf("%lld\n", bestAnswer ) ;
}
