#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(23)
#endif
constexpr i64 inf = i64(1E18);
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, M;
std::cin >> N >> M;
std::vector<std::array<int, 2>> A(N);
for (int i = 0; i < N; ++i) {
std::cin >> A[i][1] >> A[i][0];
}
std::sort(A.begin(), A.end());
debug(A);
int L = 0, R = -1;
i64 sum = 0;
std::multiset<i64> low, hgh;
auto fix = [&](int l, int r) -> i64 {
while (R < r) {
++R;
low.emplace(A[R][1]);
}
while (l < L) {
--L;
low.emplace(A[L][1]);
}
while (r < R) {
if (hgh.find(A[R][1]) != hgh.end()) {
sum -= A[R][1];
hgh.erase(hgh.find(A[R][1]));
} else {
low.erase(low.find(A[R][1]));
}
--R;
}
while (L < l) {
if (hgh.find(A[L][1]) != hgh.end()) {
sum -= A[L][1];
hgh.erase(hgh.find(A[L][1]));
} else {
low.erase(low.find(A[L][1]));
}
++L;
}
while (int(hgh.size()) > M) {
int x = *hgh.begin();
sum -= x;
hgh.erase(hgh.begin());
low.emplace(x);
}
while (int(hgh.size()) < M) {
int x = *--low.end();
sum += x;
low.erase(--low.end());
hgh.emplace(x);
}
while (!low.empty() && *hgh.begin() < *--low.end()) {
int x = *hgh.begin();
int y = *--low.end();
hgh.erase(hgh.begin());
low.erase(--low.end());
sum += y - x;
hgh.emplace(y);
low.emplace(x);
}
debug(l, r, low, hgh, sum, 2 * (A[r][0] - A[l][0]));
return sum - 2 * (A[r][0] - A[l][0]);
};
i64 ans = -inf;
auto dnq = [&](auto&& self, int l, int r, int optl, int optr) -> void {
if (l > r) {
return;
}
int mid = (l + r) >> 1;
std::pair<i64, int> opt = {-inf, -1};
for (int i = std::max(mid + M - 1, optl); i <= optr; ++i) {
i64 c = fix(mid, i);
if (c > opt.first) {
opt = {c, i};
}
}
ans = std::max(ans, opt.first);
self(self, l, mid - 1, optl, opt.second);
self(self, mid + 1, r, opt.second, optr);
};
dnq(dnq, 0, N - M, M - 1, N - 1);
std::cout << ans << '\n';
return 0;
}
