#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m;
pair <int, int> a[N];
namespace sub2 {
/// 1 2 3
/// (1 - 2) + (2 - 3) + (3 - 1)
/// 2 - 1 + 3 - 2 + 3 - 1
long long dp[2005][2005];
void solve () {
memset(dp, - 0x3f, sizeof dp);
for (int i = 1; i <= n; i++) {
dp[i][1] = a[i].first + 1LL * 2 * a[i].second;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
if (j < m) {
dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + a[i + 1].first - (j + 1 == m ? 1LL * 2 * a[i + 1].second : 0));
}
}
}
long long ans = - 1e18;
for (int i = m; i <= n; i++) {
ans = max(ans, dp[i][m]);
}
cout << ans;
}
}
namespace sub3 {
int decompress[N], pos[N];
struct FenwickTree {
long long sum[4 * N];
int cnt[4 * N];
void upd (int u, int val, int delta) {
for (int i = u; i <= n; i+= i&-i) {
sum[i]+= val;
cnt[i]+= delta;
}
}
long long walk (int num) {
long long ans = 0;
int cur = 0, pos = 0;
for (int i = 20; i >= 0; i--) {
if (pos + (1 << i) <= n && cur + cnt[pos + (1 << i)] <= num) {
ans+= sum[pos + (1 << i)];
cur+= cnt[pos + (1 << i)];
pos+= (1 << i);
}
}
return ans;
}
} fwt;
int l = 1, r = 0;
void MO(int L, int R) {
while (l > L) {
l--;
fwt.upd(pos[l], a[l].first, 1);
}
while (l < L) {
fwt.upd(pos[l], - a[l].first, - 1);
l++;
}
while (r < R) {
r++;
fwt.upd(pos[r], a[r].first, 1);
}
while (r > R) {
fwt.upd(pos[r], - a[r].first, - 1);
r--;
}
}
long long opt_ans[N];
void DnC(int L, int R, int opL, int opR) {
if (L > R) return;
int mid = L + R >> 1;
pair <long long, int> opt = make_pair (- 1e18, opL);
for (int i = opL; i <= min(mid - m + 1, opR); i++) {
MO(i + 1, mid - 1);
long long res = fwt.walk(m - 2) + a[i].first + a[mid].first + 1LL * 2 * a[i].second - 1LL * 2 * a[mid].second;
if (opt.first < res) {
opt.first = res;
opt.second = i;
}
}
opt_ans[mid] = opt.first;
DnC(L, mid - 1, opL, opt.second);
DnC(mid + 1, R, opt.second, opR);
}
void solve () {
vector <pair <int, int>> values;
for (int i = 1; i <= n; i++) {
values.push_back({- a[i].first, i});
}
sort (values.begin(), values.end());
values.resize(unique(values.begin(), values.end()) - values.begin());
for (int i = 0; i < values.size(); i++) {
decompress[i + 1] = - values[i].first;
pos[values[i].second] = i + 1;
}
DnC(1, n, 1, n);
long long ans = - 1e18;
for (int i = 1; i <= n; i++) {
ans = max(ans, opt_ans[i]);
}
cout << ans;
}
}
int32_t main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("joi19_cake3.inp", "r", stdin);
// freopen("joi19_cake3.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
sort (a + 1, a + 1 + n, [&] (pair <int, int> u, pair <int, int> v) {
return u.second < v.second;
});
return sub3::solve(), 0;
return 0;
}
