#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int MAXN=2e5+10;
const long long INF=1e15;
struct Cake {
long long v;
long long c;
};
bool cmpc(Cake a, Cake b) {
return a.c<b.c;
}
bool cmpv(Cake a, Cake b) {
return a.v>b.v;
}
struct Node {
int br;
long long sum;
};
Cake a[MAXN], b[MAXN];
Node fen[MAXN];
unordered_map <long long,int> um;
int n, m, max_st;
int curl, curr;
long long ans;
void update(int ind, int ch) {
if (ind==0) return;
ind=um[a[ind].v];
long long pl;
if (ch==1) pl=b[ind].v;
else pl=-b[ind].v;
while (ind<=n) {
fen[ind].br+=ch;
fen[ind].sum+=pl;
ind+=(ind & (-ind));
}
}
long long query(int ind) {
long long res=0;
while (ind>0) {
res+=fen[ind].sum;
ind-=(ind & (-ind));
}
return res;
}
long long findm(int k) {
int ind=max_st;
while (fen[ind].br!=k) {
if (fen[ind].br>k) ind=(ind>>1);
else {
k-=fen[ind].br;
ind+=(ind>>1);
}
}
return query(ind);
}
void move_next(int nextl, int nextr) {
while (curl>nextl) {
update(curl-1,1);
curl--;
}
while (curr<nextr) {
update(curr+1,1);
curr++;
}
while (curl<nextl) {
update(curl,-1);
curl++;
}
while (curr>nextr) {
update(curr,-1);
curr--;
}
}
void dc(int l, int r, int opl, int opr) {
if (opl>opr || l>r || l+m-1>n || l==-1 || r==-1) return;
int mid=(l+r)/2;
int start=max(mid+m-1,opl), best=-1;
long long res=-INF;
move_next(mid+1,start-1);
for (int i=start;i<=opr;i++) {
long long s=findm(m-2)+a[mid].v+a[i].v-2ll*(a[i].c-a[mid].c);
//cout << mid << ' ' << i << ' ' << s << ' ' << findm(m-2) << ' ' << a[mid].v+a[i].v << ' ' << 2*(a[i].c-a[mid].c) << endl;
if (s>res) {
res=s;
best=i;
}
update(curr+1,1);
curr++;
}
//cout << mid << ' ' << res << ' ' << best << ' ' << opl << ' ' << opr << endl;
ans=max(ans,res);
dc(l,mid-1,opl,best);
dc(mid+1,r,best,opr);
}
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i=1;i<=n;i++) {
cin >> a[i].v >> a[i].c;
b[i]=a[i];
}
sort(a+1,a+n+1,cmpc);
sort(b+1,b+n+1,cmpv);
for (int i=1;i<=n;i++) um[b[i].v]=i;
curl=curr=0;
max_st=1;
while (max_st<=n) max_st=(max_st<<1);
max_st=(max_st>>1);
ans=-INF;
dc(1,n-m+1,1,n);
cout << ans << endl;
return 0;
}
/*
8 4
112103441 501365808
659752417 137957977
86280801 257419447
902409188 565237611
965602301 689654312
104535476 646977261
945132881 114821749
198700181 915994879
5 3
2 1
4 2
6 4
8 8
10 16
*/
