#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define upmax(a,b) (a)=max((a),(b))
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
const bool debug = 0;
const int MAXN = 200055;
struct SEG {
ll ds[MAXN*4];
int dc[MAXN*4];
void push(int i, int s, int e, int x, ll r) {
ds[i] += r; dc[i]++;
if(s == e) return;
int m = (s+e) >> 1;
if(x <= m) push(i<<1, s, m, x, r);
else push(i<<1|1, m+1, e, x, r);
}
void pop(int i, int s, int e, int x, ll r) {
ds[i] -= r; dc[i]--;
if(s == e) return;
int m = (s+e) >> 1;
if(x <= m) pop(i<<1, s, m, x, r);
else pop(i<<1|1, m+1, e, x, r);
}
ll get(int i, int s, int e, int c) {
if(!c) return 0;
if(dc[i] == c) return ds[i];
int m = (s+e) >> 1;
if(c <= dc[i<<1]) return get(i<<1, s, m, c);
else return get(i<<1, s, m, dc[i<<1]) + get(i<<1|1, m+1, e, c - dc[i<<1]);
}
} seg;
int PQs, PQe;
ll A[MAXN], B[MAXN];
int AO[MAXN], ARO[MAXN];
ll Ans = -INFLL;
int N, M;
void f(int s, int e) {
for(; s < PQs;) {
PQs--;
seg.push(1, 1, N, ARO[PQs], A[PQs]);
}
for(; PQe < e;) {
PQe++;
seg.push(1, 1, N, ARO[PQe], A[PQe]);
}
for(; PQs < s;) {
seg.pop(1, 1, N, ARO[PQs], A[PQs]);
PQs++;
}
for(; e < PQe;) {
seg.pop(1, 1, N, ARO[PQe], A[PQe]);
PQe--;
}
}
void f(int s, int e, int p, int q) {
if(s > e || p > q) return;
int m = (s+e) >> 1;
ll hc = -INFLL; int hi = -1;
for(int i = max(m+M+1, p); i <= q; i++) {
f(m+1, i-1);
ll ret = seg.get(1, 1, N, M) + A[m] + B[m] + A[i] - B[i];
if(ret <= hc) continue;
hc = ret; hi = i;
}
if(debug) {
printf("F %d %d %d %d / %d %lld %d\n", s, e, p, q, m, hc, hi);
}
upmax(Ans, hc);
f(s, m-1, p, hi);
f(m+1, e, hi, q);
}
int main() {
ios::sync_with_stdio(false);
cin >> N >> M; M -= 2;
{
vector<pll> V;
for(int i = 0, a, b; i < N; i++) {
cin >> a >> b;
V.eb(b << 1, a);
}
sorv(V);
for(int i = 1; i <= N; i++)
tie(B[i], A[i]) = V[i-1];
}
iota(AO, AO+N+1, 0);
sort(AO+1, AO+N+1, [&](int a, int b) {
return A[a] > A[b];
});
for(int i = 1; i <= N; i++) ARO[AO[i]] = i;
PQs = PQe = 1;
seg.push(1, 1, N, ARO[1], A[1]);
if(debug) {
for(int i = 1; i <= N; i++)
printf("%d ; %d %lld %lld\n", i, ARO[i], A[i], B[i]);
}
f(1, N-M-1, 1, N);
cout << Ans << endl;
return 0;
}
