#include <bits/stdc++.h>
#define int long long
#define p_be second
#define p_ta first
using namespace std;
using idata = vector<int>;
using t_perle = pair<int, int>;
using t_perles = vector<t_perle>;
struct WaveletTree {
WaveletTree* left_tree = nullptr;
WaveletTree* right_tree = nullptr;
int size;
idata values;
idata cumul;
idata target_pos_left;
idata target_pos_right;
WaveletTree (idata local_values, idata sorted_values) {
size = local_values.size();
values = local_values;
cumul.resize(local_values.size() + 1);
for (int i = 0; i < size; i ++)
cumul[i + 1] = cumul[i] + local_values[i];
int pivot;
if (sorted_values.size() == 1)
pivot = sorted_values[0];
else
pivot = sorted_values[(sorted_values.size() - 1) >> 1];
target_pos_left .resize(size, 0);
target_pos_right.resize(size, 0);
idata left_values;
idata left_values_sorted;
idata right_values;
idata right_values_sorted;
for (int i = 0; i < local_values.size(); i ++) {
int u = local_values[i];
if (u <= pivot) {
left_values.push_back(u);
target_pos_left[i] ++;
} else {
right_values.push_back(u);
target_pos_right[i] ++;
}
}
for (int i = 1; i < size; i ++) {
target_pos_right[i] += target_pos_right[i - 1];
target_pos_left [i] += target_pos_left [i - 1];
}
for (int u : sorted_values) {
if (u <= pivot) left_values_sorted.push_back(u);
else right_values_sorted.push_back(u);
}
if (right_values.size() == 0) return ;
left_tree = new WaveletTree(left_values, left_values_sorted);
right_tree = new WaveletTree(right_values, right_values_sorted);
}
int sumQuery (int M, int left, int right) {
return _sumQuery(M, left, right).second;
}
pair<int, int> _sumQuery (int M, int left, int right) {
if (M < 0) {
cout << "ERROR\n";
exit(0);
}
if (left < 0 || right >= size) {
cout << "ERROR\n";
exit(0);
}
if (M == 0) return { 0, 0 };
if (right - left + 1 <= M)
return { right - left + 1, cumul[right + 1] - cumul[left] };
if (right_tree == nullptr)
return { M, cumul[M] };
pair<int, int> right_result
= right_tree->_sumQuery(
M,
left == 0 ? 0 : target_pos_right[left - 1],
target_pos_right[right] - 1
);
if (M == right_result.first) return right_result;
pair<int, int> left_result
= left_tree->_sumQuery(
M - right_result.first,
left == 0 ? 0 : target_pos_left[left - 1],
target_pos_left[right] - 1
);
return {
left_result.first + right_result.first,
left_result.second + right_result.second
};
}
void show (int depth, int left, int right) {
if (depth <= 0 || left_tree == nullptr) {
cout << "[";
for (int i = 0; i < size; i ++) {
if (left <= i && i <= right)
cout << values[i] << ":" << cumul[i + 1] << ":" << target_pos_left[i] << ":" << target_pos_right[i];
else cout << "-:-:-:-";
if (i + 1 != size)
cout << ", ";
}
cout << "]";
return ;
}
left_tree ->show(depth - 1, left == 0 ? 0 : target_pos_left [left - 1], target_pos_left [right] - 1);
right_tree->show(depth - 1, left == 0 ? 0 : target_pos_right[left - 1], target_pos_right[right] - 1);
}
void del () {
if (left_tree) left_tree->del();
if (right_tree) right_tree->del();
delete left_tree;
delete right_tree;
}
};
int N, M;
int solve (WaveletTree &queryTree, t_perles &perles,
int left, int right, int opta, int optb) {
if (left == right) return -1e18;
int mid = (left + right) >> 1;
int optm = -1;
int optv = -1e18;
for (int opti = opta; opti <= optb; opti ++) {
if (opti + M - 1 > mid) break ;
int locv = queryTree.sumQuery( M - 2, opti + 1, mid - 1 ) + 2 * (perles[opti].p_ta - perles[mid].p_ta)
+ perles[opti].p_be + perles[mid].p_be;
if (locv <= optv) continue ;
optm = opti;
optv = locv;
}
if (left + 1 == right)
return optv;
int l_optv = solve(queryTree, perles, left, mid, opta, optm);
int r_optv = solve(queryTree, perles, mid + 1, right, optm, optb);
int o_optv = max(l_optv, r_optv);
return max(optv, o_optv);
}
signed main () {
cin >> N >> M;
t_perles perles;
set<int> beauty_set;
for (int i = 0; i < N; i ++) {
int b, t;
cin >> b >> t;
beauty_set.insert(b);
perles.push_back({ t, b });
}
idata beauty_unique;
for (int u : beauty_set) beauty_unique.push_back(u);
sort(perles.begin(), perles.end());
idata beauty;
for (const auto &perle : perles)
beauty.push_back(perle.p_be);
WaveletTree queryTree (beauty, beauty_unique);
cout << solve(queryTree, perles, M, N, 0, N - 1) << endl;
queryTree.del();
}
