//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
using i128 = __int128;
using T = pair<i128, int>;
constexpr ll inf = 1e15;
constexpr i128 infl = 1e20;
struct ST {
vector<T> 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, T(-infl, 0));
}
T get(int l, int r) {
l += sz; r += sz;
T res = {-infl, 0};
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, T 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);
auto slv = [&](ll p) -> T {
T res = {-infl, 0};
for (int i = 1; i <= N; ++i) {
auto [c, v] = a[i];
T cur = T(v + 2 * c + p, 1);
if (i > 1) {
auto [pre, cnt] = tt.get(1, i);
cur = max(cur, T(pre + v + p, cnt + 1));
res = max(res, {pre + v + p - 2 * c, cnt + 1});
}
tt.upd(i, cur);
}
return res;
};
ll lx = -inf, rx = inf;
while (lx + 1 < rx) {
ll mid = (lx + rx) >> 1;
if (slv(mid).second < K) {
lx = mid;
} else {
rx = mid;
}
}
cout << ll(slv(rx).first - K * rx);
}
/*
*/
