#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200'000;
const ll INF = 1'000'000'000'000'000;
const int S = 2 * N;
int n, k;
ll v[N + 10], c[N + 10], segVal[N + 10];
int id[N + 10], cnt[4 * N + 10];
ll seg[4 * N + 10], ans[N + 10];
pair<ll, ll> p[N + 10];
int opl[S + 10], opr[S + 10];
int ql[S + 10], qr[S + 10], q;
int lft, rght;
void readInput() {
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> p[i].second >> p[i].first;
}
void calcVC() {
sort(p + 1, p + n + 1);
for (int i = 1; i <= n; i++) {
v[i] = p[i].second;
c[i] = p[i].first;
}
}
void calcId() {
for (int i = 1; i <= n; i++)
p[i] = {v[i], i};
sort(p + 1, p + n + 1);
for (int i = 1; i <= n; i++) {
segVal[i] = p[i].first;
id[p[i].second] = i;
}
}
ll get(int k, int id = 1, int l = 1, int r = n + 1) {
if (l + 1 == r)
return seg[id];
int mid = (l + r) >> 1;
if (cnt[id << 1 | 1] < k)
return seg[id << 1 | 1] + get(k - cnt[id << 1 | 1], id << 1, l, mid);
return get(k, id << 1 | 1, mid, r);
}
void update(int idx, int id = 1, int l = 1, int r = n + 1) {
if (idx < l || r <= idx)
return;
if (l + 1 == r) {
cnt[id] = 1 ^ cnt[id];
seg[id] = segVal[l] * cnt[id];
return;
}
int mid = (l + r) >> 1;
update(idx, id << 1, l, mid);
update(idx, id << 1 | 1, mid, r);
seg[id] = seg[id << 1] + seg[id << 1 | 1];
cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
}
ll getAns(int l, int r) {
while (l < lft)
update(id[lft--]);
while (rght < r)
update(id[rght++]);
while (lft < l)
update(id[++lft]);
while (r < rght)
update(id[--rght]);
if (rght - lft + 1 < k)
return -INF;
return get(k - 2) + v[lft] + v[rght] - 2ll * (c[rght] - c[lft]);
}
void addQu(int a, int b, int c, int d) {
q++;
opl[q] = a; opr[q] = b;
ql[q] = c; qr[q] = d;
}
void solve(int optL, int optR, int l, int r) {
int mid = (l + r) >> 1;
ans[mid] = getAns(optL, mid);
int opt = optL;
for (int i = optL + 1; i <= optR && i < mid; i++) {
ll tmp = getAns(i, mid);
if (tmp > ans[mid]) {
ans[mid] = tmp;
opt = i;
}
}
if (l < mid)
addQu(optL, opt, l, mid - 1);
if (mid < r)
addQu(opt, optR, mid + 1, r);
}
void calcAns() {
addQu(1, n, 1, n);
for (int i = 1; i <= q; i++)
solve(opl[i], opr[i], ql[i], qr[i]);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
readInput();
calcVC();
calcId();
calcAns();
cout << *max_element(ans + 1, ans + n + 1);
return 0;
}
