#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 {
void solve () {
}
}
int32_t main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("kieuoanh.inp", "r", stdin);
// freopen("kieuoanh.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;
});
/// for (int i = 1; i <= n; i++) cout << a[i].first << " " << a[i].second << "\n";
if (n <= 2000) return sub2::solve(), 0;
return sub3::solve(), 0;
return 0;
}
