#include <bits/stdc++.h>
using namespace std;
using ll = long long;
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
*/
const int sz = 1 << 18;
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;
}
Node(ptr _l, ptr _r) {
l = _l;
r = _r;
val = cnt = 0;
if (l) val += l->val, cnt += l->cnt;
if (r) val += r->val, cnt += r->cnt;
}
};
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 new Node(update(n->l, val, i, l, m), n->r);
else return new Node(n->l, update(n->r, val, i, m + 1, r));
}
ll walk(ptr l, ptr r, int k, int lo = 0, int hi = sz - 1) { // sum of k largest
if (lo == hi) return r->val - l->val;
int m = (lo + hi) / 2;
int rhs = r->r->cnt - l->r->cnt;
if (rhs >= k) return walk(l->r, r->r, k, m + 1, hi);
else return walk(l->l, r->l, k - rhs, lo, m) + r->r->val - l->r->val;
}
ptr roots[sz];
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 -INF;
int m = (l + r) / 2;
pl best = {-INF, -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;
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;
}
