/*******************************************
Task: JOI19_Cake3
Link: https://oj.uz/problem/view/JOI19_cake3
*******************************************/
#include <bits/stdc++.h>
#define maxn 200005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
using li = pair<int64_t, int>;
int n, k;
ii a[maxn];
li f[maxn];
li solve_lambda(int64_t lambda) {
li mx = {LLONG_MIN/100, 0};
for (int i = 1; i <= n; i++) {
f[i] = {a[i].fi + 2LL * a[i].se - lambda, 1};
f[i] = max(f[i], li{mx.fi+a[i].fi - lambda, mx.se+1});
mx = max(mx, f[i]);
}
mx = {LLONG_MIN, 0};
for (int i = 1; i <= n; i++) mx = max(mx, li{f[i].fi - 2LL * a[i].se, f[i].se});
return mx;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;
sort(a + 1, a + n + 1, [&](ii x, ii y) {return x.se < y.se;});
li mx = {-1, 0};
for (int i = 1; i <= n; i++) {
f[i] = {a[i].fi + 2LL * a[i].se, 1};
f[i] = max(f[i], li{mx.fi+a[i].fi, mx.se+1});
mx = max(mx, f[i]);
}
mx = {LLONG_MIN, 0};
for (int i = 1; i <= n; i++) mx = max(mx, li{f[i].fi - 2LL * a[i].se, f[i].se});
if (mx.se >= k) {
int64_t lo = 0, hi = LLONG_MAX/10;
while (hi - lo > 1) {
int64_t mid = (lo + hi) >> 1LL;
if (solve_lambda(mid).se >= k) lo = mid;
else hi = mid;
}
cout << solve_lambda(lo).fi + k * lo;
exit(0);
} else {
int64_t lo = -5000000000LL, hi = 1;
while (hi - lo > 1) {
int64_t mid = (lo + hi) >> 1LL;
if (solve_lambda(mid).se >= k) lo = mid;
else hi = mid;
}
cout << solve_lambda(lo).fi + max(solve_lambda(lo).se, k) * lo << "\n";
exit(0);
}
}
