#include <bits/stdc++.h>
class WaveletTree {
private:
std::vector<std::vector<int>> left;
std::vector<std::vector<int64_t>> psum;
std::vector<int> a;
public:
std::vector<std::pair<int, int>> compress;
std::vector<int> uncompressed;
int n;
WaveletTree(const std::vector<int> &_a) : a(_a), n(0) {
compress.resize(_a.size());
for (int i = 0; i < _a.size(); ++i) {
compress[i] = {_a[i], i};
}
std::sort(compress.begin(), compress.end());
std::vector<int> a(_a.size());
uncompressed.resize(_a.size());
for (int i = 0; i < _a.size(); ++i) {
if (i != 0 and compress[i].first != compress[i - 1].first) {
uncompressed[n++] = compress[i - 1].first;
}
a[compress[i].second] = n;
}
uncompressed[n++] = compress.back().first;
left.resize(4 * n), psum.resize(4 * n);
construct(1, 0, n - 1, a.begin(), a.end());
}
void construct(int v, int tl, int tr, std::vector<int>::iterator l,
std::vector<int>::iterator r) {
left[v].resize(r - l + 1), psum[v].resize(r - l + 1);
int tm = tl + (tr - tl) / 2;
for (auto it = l; it != r; ++it) {
left[v][it - l + 1] = left[v][it - l] + (*it <= tm);
psum[v][it - l + 1] = psum[v][it - l] + uncompressed[*it];
}
if (tl != tr and l != r) {
auto it = std::stable_partition(l, r, [&](int x) { return x <= tm; });
construct(2 * v, tl, tm, l, it);
construct(2 * v + 1, tm + 1, tr, it, r);
}
}
int kth(int v, int tl, int tr, int l, int r, int k) {
if (tl == tr) {
return tl;
}
int tm = (tl + tr) / 2;
int cnt = left[v][r] - left[v][l - 1];
if (k <= cnt) {
return kth(2 * v, tl, tm, left[v][l - 1] + 1, left[v][r], k);
}
return kth(2 * v + 1, tm + 1, tr, l - left[v][l - 1], r - left[v][r],
k - cnt);
}
int kth(int l, int r, int k) { return kth(1, 0, n - 1, l + 1, r + 1, k); }
std::pair<int64_t, int> sum(int v, int tl, int tr, int l, int r, int k) {
if (k < tl) {
return {0, 0};
}
if (tr <= k) {
return {psum[v][r] - psum[v][l - 1], r - l + 1};
}
int tm = (tl + tr) / 2;
auto [s1, c1] = sum(2 * v, tl, tm, left[v][l - 1] + 1, left[v][r], k);
auto [s2, c2] =
sum(2 * v + 1, tm + 1, tr, l - left[v][l - 1], r - left[v][r], k);
return {s1 + s2, c1 + c2};
}
std::pair<int64_t, int> sum(int l, int r, int k) {
return sum(1, 0, n - 1, l + 1, r + 1, k);
}
int64_t sum_k(int l, int r, int k) {
int i = kth(l, r, k);
auto [s, c] = sum(l, r, i - 1);
return s + uncompressed[i] * (k - c);
}
};
inline int nextInt() {
int64_t x = 0, c = getchar_unlocked();
while (c < '0' || c > '9') { c = getchar_unlocked(); }
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar_unlocked();
return x;
}
int main() {
const int64_t inf = 1e15;
int n = nextInt(), m = nextInt();
std::vector<std::pair<int64_t, int64_t>> a(n);
for (auto &[c, v] : a) {
v = nextInt(), c = nextInt() << 1;
}
std::sort(a.begin(), a.end());
int64_t ans = -inf;
std::vector<int> b(n);
for (int i = 0; i < n; ++i) {
b[i] = -a[i].second;
}
WaveletTree wv(b);
auto solve = [&](auto &&self, int tl, int tr, int l, int r) -> void {
if (tl > tr) {
return;
}
int tm = (tl + tr) / 2;
std::pair<int64_t, int> opt = {-inf, -1};
for (int i = std::max(l, m + tm - 1); i <= r; ++i) {
opt = std::max(opt, {a[i].second - a[i].first - wv.sum_k(tm + 1, i - 1, m - 2), i});
}
ans = std::max(ans, opt.first + a[tm].first + a[tm].second);
self(self, tl, tm - 1, l, opt.second);
self(self, tm + 1, tr, opt.second, r);
};
solve(solve, 0, n - m, 0, n - 1);
std::cout << ans << '\n';
}
