#include <bits/stdc++.h>
class WaveletTree {
private:
int low, high;
WaveletTree *left, *right;
std::vector<int> map_left;
std::vector<long long> psum;
public:
~WaveletTree() {
delete left;
delete right;
}
WaveletTree(std::vector<int>::iterator start, std::vector<int>::iterator end,
int low, int high)
: low(low), high(high), left(nullptr), right(nullptr) {
if (start >= end || low == high) {
return;
}
int mid = (low + high) / 2;
map_left.reserve(end - start + 1);
psum.reserve(end - start + 1);
map_left.push_back(0);
psum.push_back(0);
for (auto it = start; it != end; ++it) {
map_left.push_back(map_left.back() + (*it <= mid));
psum.push_back(psum.back() + *it);
}
auto pivot = std::stable_partition(start, end, [mid](int x) { return x <= mid; });
if (start != pivot) {
left = new WaveletTree(start, pivot, low, mid);
}
if (pivot != end) {
right = new WaveletTree(pivot, end, mid + 1, high);
}
}
int kth(int l, int r, int k) {
if (l > r)
return -1;
if (low == high)
return low;
int left_l = map_left[l], left_r = map_left[r + 1];
int left_count = left_r - left_l;
if (k <= left_count) {
return left->kth(left_l, left_r - 1, k);
} else {
return right->kth(l - left_l, r - left_r, k - left_count);
}
}
int kth_largest(int l, int r, int k) {
return kth(l, r, r - l + 1 - k + 1);
}
long long sum(int l, int r, int k) {
if (l > r || k < low)
return 0;
if (high <= k) {
return psum[r + 1] - psum[l];
}
int left_l = map_left[l], left_r = map_left[r + 1];
int right_l = l - left_l, right_r = r - left_r;
long long left_sum = left ? left->sum(left_l, left_r - 1, k) : 0;
long long right_sum = right ? right->sum(right_l, right_r - 1, k) : 0;
return left_sum + right_sum;
}
long long sum_largest(int l, int r, int k) {
return psum[r + 1] - psum[l] - sum(l, r, k - 1);
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
const int64_t inf = 1e15;
int n, m;
std::cin >> n >> m;
std::vector<std::pair<int64_t, int64_t>> a(n);
for (auto &[c, v] : a) {
std::cin >> v >> c;
c <<= 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.begin(), b.end(), *std::min_element(b.begin(), b.end()),
*std::max_element(b.begin(), b.end()));
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 = {-1, -1};
for (int i = l; i <= r; ++i) {
if (i - 1 - (tm + 1) + 1 < m - 2) {
continue;
}
int val = wv.kth_largest(tm + 1, i - 1, m - 2);
int64_t sum = wv.sum_largest(tm + 1, i - 1, val);
opt = std::max(opt, {a[tm].second + sum + a[i].second - (a[i].first - a[tm].first), i});
}
ans = std::max(ans, opt.first);
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';
}
