#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200'000;
const ll INF = 1000'000'000'000'000'000;
const ll BIG = 1'000'000'000'000;
int n, m;
ll a[N + 10], c[N + 10], v[N + 10];
pair<ll, int> dp[N + 10][4];
pair<ll, ll> p[N + 10];
void readInput() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> p[i].second >> p[i].first;
sort(p + 1, p + n + 1);
for (int i = 1; i <= n; i++) {
c[i] = p[i].first;
a[i] = p[i].second;
}
}
void calcDP(int i, int t) {
pair<ll, int> case1 = dp[i - 1][t];
pair<ll, int> case2 = {dp[i - 1][t - 1].first + v[i], dp[i - 1][t - 1].second + 1};
if (t == 1)
case2.first += c[i] * 2ll;
dp[i][t] = max(case1, case2);
if (t == 2) {
pair<ll, int> case3 = {dp[i - 1][t].first + v[i], dp[i - 1][t].second + 1};
dp[i][t] = max(dp[i][t], case3);
}
}
void calcDP() {
for (int i = 0; i <= n; i++)
for (int t = 0; t <= 2; t++)
dp[i][t] = {-INF, 0};
dp[0][0] = {0, 0};
for (int i = 1; i <= n; i++) {
dp[i][0] = {0, 0};
for (int t = 1; t <= 2; t++)
calcDP(i, t);
}
}
pair<ll, int> calcDP(ll x) {
for (int i = 1; i <= n; i++)
v[i] = a[i] - x;
calcDP();
pair<ll, int> res = {-INF, -1};
for (int i = 3; i <= n; i++) {
pair<ll, int> tmp = {dp[i - 1][2].first + v[i] - c[i] * 2ll, dp[i - 1][2].second + 1};
res = max(res, tmp);
}
return res;
}
void calcAns() {
ll l = -BIG, r = +BIG;
while (r - l > 1) {
ll mid = (l + r) >> 1;
pair<ll, int> res = calcDP(mid);
if (res.second >= m)
l = mid;
else
r = mid;
}
pair<ll, int> res = calcDP(l);
cout << res.first + l * m << flush;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
readInput();
calcAns();
return 0;
}
