#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#define C first
#define V second
using namespace std;
typedef pair<long long, long long> ii;
int n, m;
long long op[300005];
ii arr[200005];
struct maxM{
multiset<int> take;
multiset<int> notake;
long long total = 0;
int l = -1, r = -1;
void include(long long pos){
long long x = arr[pos].V;
if(l == -1){ ///initialise first element
l = pos; r = pos;
}
else r++; ///expand
take.insert(x); total += x;
if((int) take.size() > m){
auto it = take.begin();
total -= *it;
take.erase(it);
notake.insert(*it);
}
}
void exclude(){
long long x = arr[l].V;
l++; ///contract
auto it = notake.find(x);
if(it != notake.end()){
notake.erase(it);
return;
}
take.erase(take.find(x)); total -= x;
while((int) take.size() < m && !notake.empty()){
auto it2 = (--notake.end());
take.insert(*it2);
total += *it2;
notake.erase(it2);
}
}
long long get(){
if((int) take.size() == m) return total;
else return -1e18;
}
void reset(){
take.clear();
notake.clear();
l = -1, r = -1;
total = 0;
}
};
maxM S; ///Sliding window set: sum of the m largest integers in range [l,r]
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m; m -= 2;
for(int i = 1;i <= n;i++) cin >> arr[i].V >> arr[i].C;
sort(arr+1,arr+n+1);
fill(op,op+300004, n); op[0] = 1;
long long ans = -1e18;
for(int bit = (1<<17);bit >= 1;bit >>= 1){ ///D&C Optimization
S.reset();
for(int s = bit;s < n - m;s += 2*bit){
int L, R;
L = op[s-bit];
R = op[s+bit];
L = max(s+1, L);
long long bestValue = -1e18;
long long bestPos = -1;
for(int e = L;e <= R;e++){
long long val = S.get() + arr[s].V + arr[e].V - 2*arr[e].C + 2*arr[s].C;
ans = max(ans, val);
if(bestValue < val){
bestValue = val;
bestPos = e;
}
if(e != R){
S.include(e);
}
}
while(S.l <= s + 2*bit && S.l <= S.r){
S.exclude();
}
op[s] = bestPos;
}
}
cout << ans;
}
