#include <bits/stdc++.h>
#define int long long
#define tiiii tuple<int,int,int,int>
#define pb emplace_back
#define All(x) x.begin(), x.end()
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }
const int MAXN = 200000;
const int INF = 1e18;
int N, M;
int ans = -INF;
struct Node {
int c, v, vid;
} arr[MAXN+1];
class Seg {
private:
int cnt[MAXN*4+5];
int sum[MAXN*4+5];
void pull(int now) {
cnt[now] = cnt[now*2] + cnt[now*2+1];
sum[now] = sum[now*2] * (cnt[now*2] > 0) + sum[now*2+1] * (cnt[now*2+1] > 0);
}
public:
void build(int now=1, int l=1, int r=N) {
if (l == r) {
sum[now] = arr[l].v;
cnt[now] = 0;
return;
}
int mid = l + r >> 1;
build(now*2 , l, mid);
build(now*2+1,mid+1,r);
pull(now);
}
void mdy(int p, int k, int now=1, int l=1, int r=N) {
if (l == p && r == p) {
cnt[now] += k;
return;
} else if (l > p || r < p) return;
int mid = l + r >> 1;
mdy(p, k, now*2 , l, mid);
mdy(p, k, now*2+1,mid+1,r);
pull(now);
}
int qry(int k, int now=1, int l=1, int r=N) {
if (k == cnt[now]) {
return sum[now];
}
int mid = l + r >> 1, s = 0;
s += qry(min(cnt[now*2], k), now*2, l, mid);
if (cnt[now*2] < k)
s += qry(k - cnt[now*2], now*2+1, mid+1, r);
return s;
}
} seg;
void solve(vector<tiiii> qry) {
vector <tiiii> nxt;
int nowL = 1, nowR = 0;
for (auto [L, R, l, r] : qry) {
int mid = L + R >> 1;
int K = arr[mid].v + 2 * arr[mid].c;
pii mmax(-INF, -1);
while (nowR+1 < l) {
nowR++;
seg.mdy(arr[nowR].vid, 1);
}
while (nowL <= mid) {
seg.mdy(arr[nowL].vid, -1);
nowL++;
}
if (nowR - nowL + 1 >= M-2) {
//debug(nowR+1, K + seg.qry(M-2) + arr[nowR+1].v - 2 * arr[nowR+1].c);
mmax = max(mmax, pii(K + seg.qry(M-2) + arr[nowR+1].v - 2 * arr[nowR+1].c, nowR+1));
}
while (nowR+1 < r) {
nowR++;
seg.mdy(arr[nowR].vid, 1);
if (nowR - nowL + 1 >= M-2) {
//debug(nowR+1, K + seg.qry(M-2) + arr[nowR+1].v - 2 * arr[nowR+1].c);
mmax = max(mmax, pii(K + seg.qry(M-2) + arr[nowR+1].v - 2 * arr[nowR+1].c, nowR+1));
}
}
ans = max(ans, mmax.ff);
if (mid > L)
nxt.pb(L, mid-1, l, mmax.ss);
if (R > mid)
nxt.pb(mid+1, R, mmax.ss, r);
}
while (nowL <= nowR)
seg.mdy(arr[nowL++].vid, -1);
if (nxt.size())
solve(nxt);
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> N >> M;
for (int i = 1; i <= N; i++) {
cin >> arr[i].v >> arr[i].c;
}
sort(arr+1, arr+1+N, [](const Node a, const Node b) {
return a.v > b.v;
});
for (int i = 1; i <= N; i++) {
arr[i].vid = i;
}
seg.build();
sort(arr+1, arr+1+N, [](const Node a, const Node b) {
return a.c < b.c;
});
vector <tiiii> I;
I.pb(1, N-M+1, M, N);
solve(I);
cout << ans << '\n';
}
