#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200'000;
const ll INF = 100'000'000'000;
int n, m;
ll a[N + 10], c[N + 10], ans;
ll v[N + 10];
pair<ll, ll> p[N + 10];
pair<ll, int> dp[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;
}
}
pair<ll, int> calcDP(ll x) {
for (int i = 1; i <= n; i++)
v[i] = a[i] + x;
pair<ll, int> mx = {-INF, 0};
pair<ll, int> res = {0ll, 0};
for (int i = 1; i <= n; i++) {
pair<ll, int> case1 = {mx.first + v[i], mx.second + 1};
pair<ll, int> case2 = {v[i] + 2ll * c[i], 1};
dp[i] = max(case1, case2);
mx = max(mx, dp[i]);
if (i == 1)
res = {v[i], 1};
else
res = max(res, make_pair(dp[i].first - 2ll * c[i], dp[i].second));
}
return res;
}
void solve() {
ll l = -INF, r = INF;
while (r - l > 1) {
ll mid = (l + r) / 2ll;
if (calcDP(mid).second < m)
l = mid;
else
r = mid;
}
pair<ll, int> ans = calcDP(r);
cout << ans.first - r * ans.second << flush;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
readInput();
solve();
return 0;
}
