#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 2e5 + 5;
const ll inf = 2e15 + 5;
int n, m;
namespace DS {
multiset<int> vals;
ll sum;
vector<pii> rollback;
void print() {cerr << "#"; for(auto x : vals) cerr << x << ' '; cerr << "== " << sum << "# "; }
int gettime() {return rollback.size(); }
void insert(int x) {
vals.insert(x);
sum += x;
rollback.emplace_back(x, -1);
if(vals.size() > m)
sum -= (rollback.back().second = *vals.begin()),
vals.erase(vals.begin());
return;
}
void pop() {
if(rollback.back().second != -1)
sum += rollback.back().second,
vals.insert(rollback.back().second);
sum -= rollback.back().first;
vals.erase(vals.find(rollback.back().first));
rollback.pop_back();
return;
}
ll query() {return vals.size() != m? -2 * inf : sum;}
}
ll dp[nmax];
ll atr[nmax], v[nmax], c[nmax];
void divide(int l, int r, int optl, int optr) { // (r, optl), optl - optr, de unde poti sa iei fillere. mereu iei pozitia dupa opt_i
if(r < l) return;
int mid = l + r >> 1;
int T0 = DS::gettime();
int start;
if(r < optl) {
start = optl;
for(int i = mid + 1; i <= r; i++) {
DS::insert(v[i]);
}
}
else
start = mid + 1;
dp[mid] = -inf;
atr[mid] = -1;
//cerr << mid << ": ";
for(int i = start; i <= optr; i++) {
DS::insert(v[i]);
ll f_i = -(c[i + 1] - c[mid]) * 2 + v[mid] + v[i + 1] + DS::query();
//cerr << i << "/ ";
//DS::print();
//cerr << f_i << " ";
if(dp[mid] <= f_i)
dp[mid] = f_i,
atr[mid] = i;
}
//cerr << '\n';
assert(atr[mid] != -1);
while(DS::gettime() > T0) DS::pop();
for(int i = mid; i <= min(r, optl - 1); i++) DS::insert(v[i]);
divide(l, mid - 1, optl, atr[mid]);
while(DS::gettime() > T0) DS::pop();
for(int i = max(r + 1, optl); i < atr[mid]; i++) DS::insert(v[i]);
divide(mid + 1, r, atr[mid], optr);
return;
}
signed main() {
cin >> n >> m;
m -= 2;
vector<pii> dummy(n);
for(auto &[a, b] : dummy) cin >> b >> a;
sort(dummy.begin(), dummy.end());
//for(auto [a, b] : dummy) cerr << a << '\t' << b << '\n';
//cerr << '\n';
for(int i = 0; i < n; i++)
dp[i] = -inf,
tie(c[i], v[i]) = dummy[i];
for(int i = n - m - 1; i < m; i++) DS::insert(v[i]);
divide(0, n - m - 2, m, n - 2);
ll mx = dp[0];
for(int i = 0; i < n; i++) mx = max(mx, dp[i]);
//for(int i = 0; i < n; i++) cerr << atr[i] << ' ';
//cerr << '\n';
cout << mx << '\n';
}
/**
De-atâtea nopți aud plouând,
Aud materia plângând..
Sînt singur, și mă duce un gând
Spre locuințele lacustre.
Și parcă dorm pe scânduri ude,
În spate mă izbește-un val --
Tresar prin somn și mi se pare
Că n-am tras podul de la mal.
Un gol istoric se întinde,
Pe-același vremuri mă găsesc..
Și simt cum de atâta ploaie
Pilonii grei se prăbușesc.
De-atâtea nopți aud plouând,
Tot tresărind, tot așteptând..
Sînt singur, și mă duce-un gând
Spre locuințele lacustre.
-- George Bacovia, Lacustră
*/
