#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
mt19937 rng(1);
int n, m, v[N], c[N];
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
return abs(temp) + l;
}
ii dp[N][3];
ii maxi(ii a, ii b){
if(a.fi != b.fi) return (a.fi > b.fi ? a : b);
else return (a.se < b.se ? a : b);
}
ii cal(int ronaldo){
for(int i = 0; i <= n; i++){
for(int j = 0; j < 3; j++) dp[i][j] = {-oo, -oo};
}
dp[0][0] = {0, 0};
for(int i = 1; i <= n; i++){
dp[i][0] = {0, 0};
dp[i][1] = maxi({dp[i - 1][0].fi + v[i] + 2 * c[i] - ronaldo, dp[i - 1][0].se + 1}, {dp[i - 1][1].fi + v[i] - ronaldo, dp[i - 1][1].se + 1});
dp[i][1] = maxi(dp[i][1], dp[i - 1][1]);
dp[i][2] = maxi({dp[i - 1][1].fi + v[i] - 2 * c[i] - ronaldo, dp[i - 1][1].se + 1}, dp[i - 1][2]);
}
return dp[n][2];
}
ii arr[N];
bool cmp(ii a, ii b){
return a.se < b.se;
}
#ifdef local
void process(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> c[i];
for(int i = 1; i <= n; i++) arr[i] = {v[i], c[i]};
sort(arr + 1, arr + n + 1, cmp);
for(int i = 1; i <= n; i++){
v[i] = arr[i].fi;
c[i] = arr[i].se;
}
int le = -2e12, ri = 2e12;
int answer = -oo;
while(le < ri - 2){
int mid = (le + ri) >> 1;
ii temp = cal(mid);
if(temp.se >= m) le = mid;
else ri = mid;
// cout << le << " " << ri << " " << temp.fi << " " << temp.se << "\n";
// if(temp.se <= m) answer = max(answer, temp.fi - m * temp.se);
}
for(int i = le; i <= ri; i++){
ii temp = cal(i), temp2 = cal(i - 1);
// cout << i << " " << temp.fi << " " << temp.se << " " << temp2.fi << " " << temp2.se << "\n";
if(temp.se <= m && temp2.se >= m) answer = max(answer, temp.fi + (temp.se) * i);
}
cout << answer << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
process();
}
#endif
