#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first
#define vs second
const int mod = 1000000007;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 200004;
int n , m;
vector<pair<ll,ll>> arr;
ll ans;
bool cmp(pair<int,int> a , pair<int,int> b){
if(a.vs == b.vs)return a.vf > b.vf;
return a.vs < b.vs;
}
struct item {
vector<int> left , right;
};
/*void unite(vector<int>& a , vector<int>& b){
vector<int> v;
for(int i : a)v.pb(i);
for(int i : b)v.pb(i);
if(v.size() < m){
return;
}
cout << "printing v\n";
for(int i : v)cout << i << ' ';
cout << '\n';
cout << "printing v completed\n";
bool vis[v.size()];
memset(vis,0,sizeof vis);
int j = 0;
int last = 1;
set<pair<ll,int>> s;
ll res = 0;
ll tp[v.size()];
for(int i = 1; i < m; i++){
res += arr[v[i]].vf;
s.insert(mp(arr[v[i]].vf , i));
tp[i] = arr[v[i]].vf;
}
res -= 2*(arr[v[m-1]].vs - arr[v[0]].vs);
res += arr[v[0]].vf;
ans = max(ans , res);
cout << res << '\n';
s.insert(mp(arr[v[0]].vf - 2*(arr[v[last]].vs - arr[v[j]].vs) , 0));
tp[0] = arr[v[0]].vf - 2*(arr[v[last]].vs - arr[v[j]].vs);
for(int i = m; i < v.size(); i++){
res -= 2*(arr[v[i]].vs - arr[v[i-1]].vs);
ll val = arr[v[i]].vf;
if(val >= ((*s.begin()).vf)){
pair<ll,int> p = *s.begin();
s.erase(s.begin());
//cout << p.vf << ' ';
res -= p.vf;
res += val;
vis[p.vs] = 1;
s.insert(mp(val, i));
tp[i] = val;
}
else vis[i] = 1;
while(j < v.size() && vis[j]){
j++;
}
last = max(last , j + 1);
while(last < v.size() && vis[last]){
last++;
}
if(s.count(mp(tp[j] , j))){
s.erase(mp(tp[j] , j));
tp[j] = arr[v[j]].vf - 2*(arr[v[last]].vs - arr[v[j]].vs);
s.insert(mp(tp[j] , j));
}
else {
while(1){
;
}
}
ans = max(ans , res);
cout << res << '\n';
}
}*/
void unite(vector<int>& a , vector<int>& b){
if(a.size() + b.size() < m)return;
ll left[a.size() + 1] , right[b.size() + 1];
left[0] = right[0] = 0;
ll pre[a.size()] , suf[b.size()];
int idx_pre[a.size()] , idx_suf[b.size()];
pre[0] = arr[a[0]].vf - 2*(arr[a.back()].vs - arr[0].vs);
idx_pre[0] = 0;
suf[b.size()-1] = arr[b.back()].vf - 2*(arr[b.back()].vs - arr[b[0]].vs);
idx_suf[b.size()-1] = b.size()-1;
for(int i = 1; i < a.size(); i++){
ll cur = arr[a[i]].vf - 2*(arr[a.back()].vs - arr[a[i]].vs);
if(cur > pre[i-1]){
pre[i] = cur;
idx_pre[i] = i;
}
else {
pre[i] = pre[i-1];
idx_pre[i] = idx_pre[i-1];
}
}
for(int i = b.size()-2; i >= 0; i--){
ll cur = arr[b[i]].vf - 2*(arr[b[i]].vs - arr[b[0]].vs);
if(cur > suf[i + 1]){
suf[i] = cur;
idx_suf[i] = i;
}
else {
suf[i] = suf[i + 1];
idx_suf[i] = idx_suf[i + 1];
}
}
priority_queue<ll> pq;
int r = a.size()-1;
int last = r;
for(int i = 1; i <= a.size(); i++){
if(r >= 0){
if(pq.size() == 0 || pre[r] + 2*(arr[a.back()].vs - arr[a[last]].vs) >= pq.top()){
left[i] = left[i-1] + pre[r] + 2*(arr[a.back()].vs - arr[a[last]].vs);
int nr = idx_pre[r];
for(int j = r; j > nr; j--){
pq.push(arr[a[j]].vf);
}
last = nr;
r = nr-1;
}
else {
left[i] = left[i-1] + pq.top();
pq.pop();
}
}
else {
left[i] = left[i-1] + pq.top();
pq.pop();
}
}
r = 0;
last = 0;
while(pq.size())pq.pop();
for(int i = 1; i <= b.size(); i++){
if(r < b.size()){
if(pq.size() == 0 || suf[r] + 2*(arr[b[last]].vs - arr[b[0]].vs) >= pq.top()){
right[i] = right[i-1] + suf[r] + 2*(arr[b[last]].vs - arr[b[0]].vs);
int nr = idx_suf[r];
for(int j = r; j < nr; j++){
pq.push(arr[b[j]].vf);
}
last = nr;
r = nr + 1;
}
else {
right[i] = right[i-1] + pq.top();
pq.pop();
}
}
else {
right[i] = right[i-1] + pq.top();
pq.pop();
}
}
ll dif = 2*(arr[b[0]].vs - arr[a.back()].vs);
/*for(int i = 0; i <= a.size(); i++){
cout << left[i] << ' ';
}
cout << '\n';
for(int i = 0; i <= b.size(); i++){
cout << right[i] << ' ';
}
cout << '\n';*/
for(int i = 1; i <= a.size(); i++){
if(m - i <= b.size()){
//cout << left[i] << ' ' << right[m-i] << ' ' << dif << '\n';
ans = max(ans , left[i] + right[m-i] - dif);
}
}
//cout << '\n';
}
vector<int> left_merge(vector<int>& a , vector<int>& b , bool rev){
vector<int> v;
for(int i : a)v.pb(i);
for(int i : b)v.pb(i);
if(v.size() <= m){
return v;
}
if(rev)reverse(all(v));
priority_queue<pair<int,int>,vector<pair<int,int>> , greater<pair<int,int>> > pq;
ll res = 0;
for(int i = 0; i < m; i++){
res += arr[v[i]].vf;
pq.push(mp(arr[v[i]].vf , i));
if(i){
res -= 2*abs(arr[v[i]].vs - arr[v[i-1]].vs);
}
}
ll best[v.size()];
best[m-1] = res;
for(int i = m; i < v.size(); i++){
res -= 2*abs(arr[v[i]].vs - arr[v[i-1]].vs);
if(pq.top().vf < arr[v[i]].vf){
res -= pq.top().vf;
pq.pop();
pq.push(mp(arr[v[i]].vf , i));
res += arr[v[i]].vf;
}
best[i] = res;
}
int pos = m-1;
res = best[m-1];
for(int i = m; i < v.size(); i++){
if(best[i] > res){
pos = i;
res = best[i];
}
}
/*cout << "printing best\n";
for(int i = m - 1; i < v.size(); i++){
cout << best[i] << ' ';
}
cout << '\n';
cout << "printing best completed\n";*/
while(pq.size())pq.pop();
for(int i = 0; i < m; i++){
pq.push(mp(arr[v[i]].vf , v[i]));
}
for(int i = m; i <= pos; i++){
if(pq.top().vf < arr[v[i]].vf){
pq.pop();
pq.push(mp(arr[v[i]].vf , v[i]));
}
}
vector<int> toreturn;
while(pq.size()){
toreturn.pb(pq.top().vs);
pq.pop();
}
sort(all(toreturn));
return toreturn;
}
item merge(item a , item b){
unite(a.right , b.left);
vector<int> left = left_merge(a.left , b.left , 0);
vector<int> right = left_merge(a.right , b.right , 1);
/*cout << "printing left\n";
for(int i : left){
cout << i << ' ';
}
cout << '\n';
cout << "printing right\n";
for(int i : right){
cout << i << ' ';
}
cout << '\n';*/
return {left , right};
}
item dnc(int l , int r){
//cout << "came" << endl;
if(l == r){
return {{l} , {l}};
}
int m = (l + r)/2;
item a = dnc(l , m);
item b = dnc(m + 1 , r);
//cout << l << ' ' << r << '\n';
return merge(a , b);
}
void solve(){
cin >> n >> m;
for(int i = 0; i < n; i++){
int x , y;
cin >> x >> y;
arr.pb(mp(x,y));
}
sort(all(arr),cmp);
/*for(int i = 0; i < n; i++){
cout << arr[i].vf << ' ' << arr[i].vs << '\n';
}
cout << "array printing completed\n";*/
ans = -1e9;
dnc(0,n-1);
cout << ans << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//int t;
//cin >> t;
//while(t--)
solve();
}
