/* AUTHOR: TUAN ANH - BUI */
// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
template<class X, class Y>
bool minimize(X &x, const Y &y) {
if (x > y) return x = y, true;
return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
if (x < y) return x = y, true;
return false;
}
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebear"
/*END OF TEMPLATE. ICEBEAR AND THE CAT WILL WIN VOI26 */
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 27092008;
const ll INF = (ll)1e18 + 27092008;
const int N = 2e5 + 5;
int numPiece, numChoose;
ll best[N];
int compress[N];
struct Piece {
int beauty, color, index;
bool operator < (const Piece &other) const {
return color < other.color;
}
} piece[N];
struct FenwickTree {
int sizeTree;
vector<int> cnt;
vector<ll> ft;
FenwickTree(int n = 0): sizeTree(n), cnt(n + 5, 0), ft(n + 5, 0) {}
void update(int x, int val) {
for(; x <= sizeTree; x += x & -x) {
ft[x] += val;
cnt[x] += (val < 0 ? -1 : +1);
}
}
ll walk(int num) {
ll sum = 0;
int pos = 0, cur = 0;
RED(i, 20) {
if (pos + MASK(i) <= sizeTree && cur + cnt[pos + MASK(i)] <= num) {
pos += MASK(i);
sum += ft[pos];
cur += cnt[pos];
}
}
return sum;
}
} ft;
bool comp(const Piece &X, const Piece &Y) {
return X.beauty > Y.beauty;
}
int L = 1, R = 0;
void MO(int l, int r) {
while(L > l) --L, ft.update(compress[piece[L].index], piece[L].beauty);
while(R < r) ++R, ft.update(compress[piece[R].index], piece[R].beauty);
while(L < l) ft.update(compress[piece[L].index], -piece[L].beauty), L++;
while(R > r) ft.update(compress[piece[R].index], -piece[R].beauty), R--;
}
void DnC(int l, int r, int optL, int optR) {
if (l > r || optL > optR) return;
int mid = (l + r) >> 1;
pair<ll, int> opt = mp(-INF, optL);
FOR(i, optL, min(mid - numChoose + 1, optR)) {
MO(i + 1, mid - 1);
maximize(opt, mp(ft.walk(numChoose - 2) + piece[mid].beauty + piece[i].beauty - 2 * piece[mid].color + 2 * piece[i].color, i));
}
best[mid] = opt.first;
DnC(l, mid - 1, optL, opt.second);
DnC(mid + 1, r, opt.second, optR);
}
void init(void) {
cin >> numPiece >> numChoose;
FOR(i, 1, numPiece) cin >> piece[i].beauty >> piece[i].color, piece[i].index = i;
}
void process(void) {
sort(piece + 1, piece + numPiece + 1, comp);
FOR(i, 1, numPiece) compress[piece[i].index] = i;
sort(piece + 1, piece + numPiece + 1);
ft = FenwickTree(numPiece);
DnC(1, numPiece, 1, numPiece);
cout << *max_element(best + 1, best + numPiece + 1);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int tc = 1;
// cin >> tc;
while(tc--) {
init();
process();
}
return 0;
}
