#include <bits/stdc++.h>
#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];
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);
long long ans = -1e18;
fill(op,op+300004, n); op[0] = 1;
for(int bit = (1<<17);bit >= 1;bit >>= 1){
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;
priority_queue<long long, vector<long long>, greater<long long> > pq;
long long acc = 0;
for(int e = L;e <= R;e++){
if((int) pq.size() >= m){
if((int) pq.size() > m){
acc -= pq.top();
pq.pop();
}
long long val = acc + 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;
}
}
pq.push(arr[e].V);
acc += arr[e].V;
}
op[s] = bestPos;
}
}
cout << ans;
}
