#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
using pl = pair<ll,ll>;
#define vt vector
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define F0R(i, b) FOR(i, 0, b)
#define endl '\n'
#define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0)
const ll INF = 1e18;
/*
as l increases, the optimal r also increases
*/
using ptr = struct Node*;
struct Node {
ll val;
int cnt;
ptr l, r;
Node(ll _val, int _cnt): val(_val), cnt(_cnt) {
l = r = 0;
}
};
const int sz = 1 << 18;
vt<ptr> roots;
ptr pull(ptr l, ptr r) {
ptr res = new Node(l->val + r->val, l->cnt + r->cnt);
res->l = l;
res->r = r;
return res;
}
ptr update(ptr n, ll val, int i, int l = 0, int r = sz - 1) {
if (l == r) return new Node(val, 1);
int m = (l + r) / 2;
if (i <= m) return pull(update(n->l, val, i, l, m), n->r);
else return pull(n->l, update(n->r, val, i, m + 1, r));
}
ll walk(ptr ln, ptr rn, int k, int l = 0, int r = sz - 1) {
if (l == r) return k ? rn->val - ln->val : 0ll;
int m = (l + r) / 2;
int rhs = rn->r->cnt - ln->r->cnt;
if (rhs >= k) return walk(ln->r, rn->r, k, m + 1, r); // go right
else return walk(ln->l, rn->l, k - rhs, l, m) + rn->r->val - ln->r->val;
}
int n, k;
vt<pl> cakes;
ll query(int l, int r) {
if (l > r) return 0ll;
return walk(roots[l], roots[r + 1], k - 2);
}
ll dnc(int l, int r, int lo, int hi) {
if (l > r) return 0ll;
int m = (l + r) / 2;
pl best = {0, -1};
FOR (i, lo, hi + 1) {
if (i - m + 1 < k) continue;
ll val = query(m + 1, i - 1) - (cakes[i].f - cakes[m].f) + cakes[i].s + cakes[m].s;
best = max(best, pl{val, i});
}
return max({best.f, dnc(l, m - 1, lo, best.s), dnc(m + 1, r, best.s, hi)});
}
main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
cakes.resize(n); // colour, value
F0R (i, n) cin >> cakes[i].s >> cakes[i].f, cakes[i].f *= 2;
sort(all(cakes));
vt<pl> sorted(n);
F0R (i, n) sorted[i] = {cakes[i].s, i};
sort(all(sorted));
vt<int> rind(n);
F0R (i, n) rind[sorted[i].s] = i;
roots.resize(n + 1);
ptr root = new Node(0, 0);
roots[0] = root->l = root->r = root;
F0R (i, n) {
roots[i + 1] = update(roots[i], cakes[i].s, rind[i]);
}
cout << dnc(0, n - 1, 0, n - 1) << endl;
}
