#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"
void printVector(vector<int> a){
for (auto x: a) cout << x << " ";
cout << endl;
}
int n, m;
vector<pair<int, int>> cakes;
vector<int> val;
void dnc(int l, int r, int optl, int optr){
if (l > r) return;
int mid = (l+r)/2;
if (n-mid < m-1) return;
pair<int, int> best = {-1e17, mid};
multiset<int> o; int u = 0;
for (int j = mid+1; j < mid+m-1; ++j){
o.insert(cakes[j].second);
u += cakes[j].second;
}
// if (mid == 3) cout << u << endl;
for (int j = mid+m-1; j <= optr; j++){
int t = cakes[mid].second+cakes[j].second+u-2*(cakes[j].first-cakes[mid].first);
best = max(best, {t, j});
// if (mid == 3) cout << t << endl;
if (cakes[j].second > *(o.begin())){
u -= *(o.begin());
o.erase(o.begin());
o.insert(cakes[j].second);
u += cakes[j].second;
}
}
// cout << mid << best.first << best.second << endl;
val[mid] = best.first;
int opt = best.second;
dnc(l, mid-1, optl, opt);
dnc(mid+1, r, opt, optr);
}
void solve(){
cin >> n >> m;
cakes.pb({-1,-1});
val.resize(n+1);
FOR(i,0,n){
int v, c; cin >> v >> c;
cakes.pb({c, v});
}
sort(all(cakes));
dnc(1, n, 1, n);
int ans = 0;
// printVector(val);
FOR(i,1,n+1) ans = max(ans, val[i]);
cout << ans << endl;
}
int32_t main(){
ios::sync_with_stdio(false);cin.tie(nullptr);
int t = 1; // cin >> t;
while (t--) solve();
}
