#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int n, m, inCnt, smallestV, rem;
LL sumV;
map<int, int> cnt;
vector<LL> f;
struct Piece {
int v, c;
Piece(int _v = 0, int _c = 0) : v(_v), c(_c) {}
bool operator<(const Piece &_) const { return make_pair(c, v) < make_pair(_.c, _.v); }
};
vector<Piece> piece;
void add(int val) {
++cnt[val];
if (inCnt < m) {
sumV += val;
tie(smallestV, rem) = *cnt.begin();
}
else {
if (val > smallestV) {
sumV -= smallestV, sumV += val;
if (rem == 1) tie(smallestV, rem) = *cnt.upper_bound(smallestV);
else --rem;
}
}
++inCnt;
}
void eli(int val) {
int nSmallestV = cnt[smallestV];
--cnt[val];
if (!cnt[val]) cnt.erase(val);
if (inCnt <= m) {
sumV -= val;
tie(smallestV, rem) = *cnt.begin();
}
else {
if (val >= smallestV) {
if (rem == nSmallestV) {
sumV -= val;
smallestV = prev(cnt.lower_bound(smallestV) )->first;
rem = 1;
sumV += smallestV;
}
else {
++rem;
sumV -= val;
sumV += smallestV;
}
}
}
--inCnt;
}
void solve(int Left, int Right, int l, int r) {
int Mid = (Left + Right) >> 1;
if (Mid < m + 1) {
if (Mid < Right) solve(Mid + 1, Right, l, r);
return ;
}
for (int i = r; i >= Mid - 1; --i) add(piece[i].v);
for (int i = Right; i >= Mid; --i) eli(piece[i].v);
int opt = -1;
for (int i = min(Mid - 2, r); i >= l; --i) {
LL tmp = sumV - 2 * (piece[Mid].c - piece[i].c) + piece[Mid].v + piece[i].v;
if (f[Mid] <= tmp) {
f[Mid] = tmp;
opt = i;
}
add(piece[i].v);
}
for (int i = l; i <= opt; ++i) eli(piece[i].v);
if (Left < Mid) solve(Left, Mid - 1, l, opt);
for (int i = Mid; i <= Right; ++i) add(piece[i].v);
for (int i = opt + 1; i <= r; ++i) eli(piece[i].v);
if (Mid < Right) solve(Mid + 1, Right, opt, r);
}
int main() {
// freopen("input", "r", stdin);
scanf(" %d %d", &n, &m); m -= 2;
piece.assign(n, Piece() );
for (int i = 0; i < n; ++i) {
int v, c; scanf(" %d %d", &v, &c);
piece[i] = Piece(v, c);
}
sort(piece.begin(), piece.end() );
f.assign(n, 0);
solve(0, n - 1, 0, n - 1);
LL ans = 0;
for (LL ret : f) ans = max(ans, ret);
cout << ans;
return 0;
}
