#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
namespace Treap {
struct Node {
int prior, sz;
int value;
long long sum;
Node *l = NULL, *r = NULL;
Node() : prior(rnd()), sz(1), value(0), sum(0) {}
Node(int v) : prior(rnd()), sz(1), value(v), sum(v) {}
};
using pt = Node*;
int sz(pt t) { return t ? t->sz : 0; }
long long sum(pt t) { return t ? t->sum : 0; }
void pull(pt t) {
if (t) {
t->sum = sum(t->l) + sum(t->r) + t->value;
t->sz = sz(t->l) + sz(t->r) + 1;
}
}
void split_sz(pt t, pt &l, pt &r, int key) { // sz(l) = key
if (!t) return void(l = r = NULL);
int id = sz(t->l) + 1;
if (id <= key) {
split_sz(t->r, t->r, r, key - id), l = t;
} else {
split_sz(t->l, l, t->l, key), r = t;
}
pull(t);
}
void split_val(pt t, pt &l, pt &r, int key) { // val(l) <= key
if (!t) return void(l = r = NULL);
if (t->value <= key) {
split_val(t->r, t->r, r, key), l = t;
} else {
split_val(t->l, l, t->l, key), r = t;
}
pull(t);
}
void merge(pt &t, pt l, pt r) {
if (!l || !r) {
t = l ? l : r;
} else if (l->prior > r->prior) {
merge(l->r, l->r, r), t = l;
} else {
merge(r->l, l, r->l), t = r;
}
pull(t);
}
void erase(pt &t, int key) {
if (!t) return;
if (t->value == key) {
pt del = t;
merge(t, t->l, t->r);
delete del;
} else if (t->value < key) {
erase(t->r, key);
} else {
erase(t->l, key);
}
pull(t);
}
void insert(pt &t, int x) { // insert value x to the treap
pt l, r;
split_val(t, l, r, x);
merge(l, l, new Node(x));
merge(t, l, r);
}
long long query(pt &t, int k) { // sum of k largest in treap
pt l, r;
int key = sz(t) - k;
split_sz(t, l, r, key);
long long res = sum(r);
merge(t, l, r);
return res;
}
}
struct Cake {
int V, C;
Cake() {}
Cake(int V, int C) : V(V), C(C) {}
};
int N, M;
vector<Cake> cake;
Treap::Node *treap = NULL;
long long Query(int l, int r) {
if (r - l + 1 < M) return -INF;
static int tl = 0, tr = 0;
while (tr < r + 1) Treap::insert(treap, cake[tr++].V);
while (tl > l) Treap::insert(treap, cake[--tl].V);
while (tr > r + 1) Treap::erase(treap, cake[--tr].V);
while (tl < l) Treap::erase(treap, cake[tl++].V);
return Treap::query(treap, M) - 2 * (cake[r].C - cake[l].C);
}
long long Solve(int L1, int L2, int R1, int R2) {
if (L1 > L2 || R1 > R2) return -INF;
int L = (L1 + L2) / 2;
int opt = R1;
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({Solve(L1, L - 1, R1, opt), Solve(L + 1, L2, opt, R2), cur});
}
int main() {
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), [&](Cake a, Cake b) { return a.C < b.C || (a.C == b.C && a.V < b.V); });
cout << Solve(0, N - M, 0, N - 1) << "\n";
return 0;
}
