#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define int long long
const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll blocks = 350;
ll n,m, L = 0, R = 0;
pll a[N];
ll c[N], dp[N];
vector<pll>v;
struct segment_tree{
ll n;
vector<pair<ll,int>>st;
void init(int _n){
n = _n;
st.resize(4 * n + 10);
}
pair<ll,int> merge(const pair<ll,int> &a, const pair<ll,int> &b){
return {a.F + b.F, a.S + b.S};
}
void update(int id, int l, int r, int pos, ll val, int typ){
if(l > pos || r < pos) return;
if(l == r){
st[id].F += val * typ;
st[id].S += typ;
return;
}
int mid = (l + r) / 2;
update(2 * id, l, mid, pos, val, typ);
update(2 * id + 1, mid + 1, r, pos, val, typ);
st[id] = merge(st[2 * id], st[2 * id + 1]);
}
pair<ll,int> get(int id, int l, int r, int left, int right){
if(l > right || r < left) return {0, 0};
if(left <= l && r <= right) return st[id];
int mid = (l + r) / 2;
return merge(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
}
int walk(int id, int l, int r, int val){
if(l == r) return l;
int mid = (l + r) / 2;
if(st[2 * id + 1].S > val) return walk(2 * id + 1, mid + 1, r, val);
else if(st[id].S > val) return walk(2 * id, l, mid, val - st[2 * id + 1].S);
else return -1;
}
pair<ll,int> get(int l, int r){return get(1,1,n,l,r);}
void update(int pos, ll val, ll typ){update(1,1,n,pos,val,typ);}
} st;
void update(ll l, ll r){ // them tu 1 den r, xoa tu 1 den l - 1
while(R < r){
R++;
st.update(c[R], a[R].F, 1);
}
while(R > r){
st.update(c[R], a[R].F, -1);
R--;
}
while(L < l - 1){
L++;
st.update(c[L], a[L].F, -1);
}
while(L > l - 1){
st.update(c[L], a[L].F, 1);
L--;
}
}
void dnc(ll l, ll r, ll optl, ll optr){
if(l > r) return;
pll res = {-inf, -1};
ll mid = (l + r) / 2;
for(int i = max(1ll, optl - 1); i <= min(mid - m + 1, optr);i++){
update(i + 1, mid - 1);
ll pos = st.walk(1,1,n,m-2);
if(pos == -1) pos = 1;
else pos++;
ll x = st.get(pos, n).F;
res = max(res, {x + a[i].F + a[mid].F - 2 * (a[mid].S - a[i].S), i});
}
dp[mid] = res.F;
ll opt = res.S;
dnc(l, mid - 1, optl, opt);
dnc(mid + 1, r, opt, optr);
}
void to_thic_cau(){
cin >> n >> m;
for(int i = 1; i <= n;i++){
cin >> a[i].F >> a[i].S;
}
sort(a + 1, a + n + 1, [&](const pll &a, const pll &b){
return a.S < b.S;
});
for(int i = 1; i <= n;i++) v.pb({a[i].F, i});
sort(all(v));
for(int i = 0; i < v.size();i++) c[v[i].S] = i + 1;
st.init(n);
dnc(1,n,1,n);
ll res = -inf;
for(int i = 1; i <= n;i++) res = max(res, dp[i]);
cout << res << "\n";
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll tc = 1;
//cin >> tc;
while(tc--) to_thic_cau();
}
