//I wrote this code 4 u <3
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;
struct ST {
vector<ll> t;
int sz;
void pull(int i) {
t[i] = max(t[i << 1], t[i << 1 | 1]);
}
ST(int n) {
sz = 1;
while (sz < n) sz <<= 1;
t.resize(sz << 1, -inf);
}
void init(vector<ll>& a) {
for (int i = 0; i < (int) a.size(); ++i) t[i + sz] = a[i];
for (int i = sz - 1; i > 0; --i) pull(i);
}
ll get(int l, int r) {
l += sz; r += sz;
ll res = -inf;
while (l < r) {
if (l & 1) res = max(res, t[l++]);
if (r & 1) res = max(res, t[--r]);
l >>= 1; r >>= 1;
}
return res;
}
void upd(int i, ll v) {
i += sz;
t[i] = v;
i >>= 1;
while (i) {
pull(i);
i >>= 1;
}
}
};
signed main(int32_t argc, char *argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
cin >> N >> K;
vector<array<ll, 2>> a(N + 1);
for (int i = 1; i <= N; ++i) cin >> a[i][1] >> a[i][0];
sort(a.begin() + 1, a.end());
ST tt(N + 1);
tt.upd(0, 0ll);
vector<vector<ll>> dp(K + 1, vector<ll>(N + 1));
for (int k = 1; k < K; ++k) {
for (int i = k; i <= N; ++i) {
auto [c, v] = a[i];
if (k == 1) {
dp[k][i] = v + 2 * c;
} else {
dp[k][i] = tt.get(0, i) + v;
}
}
tt.init(dp[k]);
}
ll ans = -inf;
for (int i = K; i <= N; ++i) {
auto [c, v] = a[i];
ans = max(ans, v - 2 * c + tt.get(0, i));
}
cout << ans;
}
/*
*/
