#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
class SegmentTree {
private:
int sz;
vector<int> A;
vector<pair<long long, int>> tree;
void Update(int n, int tl, int tr, int pos, int activate) {
if (tl == tr) return void(tree[n] = {activate ? A[pos] : 0, activate});
int mid = (tl + tr) / 2;
int lc = n + 1;
int rc = n + 2 * (mid - tl + 1);
if (pos <= mid) {
Update(lc, tl, mid, pos, activate);
} else {
Update(rc, mid + 1, tr, pos, activate);
}
tree[n] = {tree[lc].first + tree[rc].first, tree[lc].second + tree[rc].second};
}
long long Query(int n, int tl, int tr, int key) { // sum of key minimum elements
if (key <= 0) return 0;
if (tree[n].second <= key) return tree[n].first;
int mid = (tl + tr) / 2;
int lc = n + 1;
int rc = n + 2 * (mid - tl + 1);
return Query(lc, tl, mid, key) + Query(rc, mid + 1, tr, key - tree[lc].second);
}
public:
SegmentTree() {}
SegmentTree(int n, vector<int> A) : sz(n), A(A) {
tree.resize(2 * sz);
}
void Insert(int pos) {
return Update(1, 0, sz - 1, pos, 1);
}
void Erase(int pos) {
return Update(1, 0, sz - 1, pos, 0);
}
long long Query(int key) { // return key largest elements
return tree[1].first - Query(1, 0, sz - 1, tree[1].second - key);
}
};
struct Cake {
int V, C;
Cake() {}
Cake(int V, int C) : V(V), C(C) {}
};
int N, M;
vector<Cake> cake;
SegmentTree seg;
vector<int> coord;
void Init() { // coordinate compression on cake based on V, cakes initially sorted by C
vector<pair<int, int>> all;
for (int i = 0; i < N; i++) {
all.emplace_back(cake[i].V, i);
}
sort(begin(all), end(all));
coord.resize(N);
for (int i = 0; i < N; i++) {
coord[all[i].second] = i;
}
vector<int> A;
for (int i = 0; i < N; i++) {
A.emplace_back(all[i].first);
}
seg = SegmentTree(N, A);
}
long long Query(int l, int r) {
if (r - l + 1 < M) return -INF;
static int tl = 0, tr = -1;
while (tr < r) seg.Insert(coord[++tr]);
while (tl > l) seg.Insert(coord[--tl]);
while (tr > r) seg.Erase(coord[tr--]);
while (tl < l) seg.Erase(coord[tl++]);
return seg.Query(M) - 2 * (cake[r].C - cake[l].C);
}
long long Solve(int L1 = 0, int L2 = N - M, int R1 = 0, int R2 = N - 1) {
if (L1 > L2) return -INF;
int L = (L1 + L2) / 2;
int opt = -1;
long long cur = -INF;
for (int R = max(R1, L + M - 1); R <= R2; R++) {
long long now = Query(L, R);
if (now > cur) cur = now, opt = R;
}
return max({cur, Solve(L1, L - 1, R1, opt), Solve(L + 1, L2, opt, R2)});
}
void Read() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> N >> M;
cake.resize(N);
for (int i = 0; i < N; i++) {
cin >> cake[i].V >> cake[i].C;
}
sort(begin(cake), end(cake), [&](const Cake &a, const Cake &b) {
return make_pair(a.C, a.V) < make_pair(b.C, b.V);
});
}
int main() {
Read();
Init();
cout << Solve() << "\n";
return 0;
}
