#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
//#define all(x) x.begin(),x.end()
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define inf 2000000000000000
#define N 300005
#define MOD 998244353
#define KOK 700
using namespace std;
int n,m;
int p[2]={1,0};
ii a[N];
ll ans[N];
ll Maxm;
multiset<int> all,best;
int tut[N];
void del(int val) {
all.erase(all.find(val));
auto pos=best.find(val);
if(pos!=best.end()) {
Maxm-=tut[val];
best.erase(pos);
if(sz(all)!=sz(best)) {
auto pos2=prev(all.lower_bound(*best.begin()));
best.insert(*pos2);
Maxm+=tut[*pos2];
}
}
}
void add(int val) {
all.insert(val);
best.insert(val);
Maxm+=tut[val];
if(sz(best)==m+1) {
Maxm-=tut[*best.begin()];
best.erase(best.begin());
}
}
void shift(int w,int to) {
if(w==0) {
while(p[0]-1>=to) {
--p[0];
add(a[p[0]].st);
}
while(p[0]<to) {
del(a[p[0]].st);
++p[0];
}
}
else {
while(p[1]+1<=to) {
++p[1];
add(a[p[1]].st);
}
while(p[1]>to) {
del(a[p[1]].st);
--p[1];
}
}
}
void make(int lw,int rw) {
if(lw<=p[0]) shift(0,lw);
if(rw>=p[1]) shift(1,rw);
shift(0,lw);
shift(1,rw);
}
void f(int bas,int son,int l,int r) {
if(bas>son) return ;
int pos=orta;
int curr=min(r,pos);
make(curr,pos);
ans[pos]=-inf;
int to=-1;
for(int i=curr;i>=l;i--,shift(0,i)) {
if(pos-i+1<m) continue;
ll cur=Maxm-2*(a[pos].nd-a[i].nd);
if(cur>=ans[pos]) {
ans[pos]=cur;
to=i;
}
}
if(to==-1) {
for(int i=bas;i<=pos;i++) ans[i]=-inf;
return ;
}
f(bas,pos-1,l,to);
f(pos+1,son,to,r);
}
int main() {
map<int,int> mp;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) {
scanf("%d %d",&a[i].st,&a[i].nd);
mp[a[i].st]++;
}
int cnt=0;
for(auto x:mp) {
for(int i=0;i<x.nd;i++) {
tut[++cnt]=x.st;
}
}
for(int i=1;i<=cnt;i++) {
while(i+1<=cnt && tut[i]==tut[i+1]) i++;
mp[tut[i]]=i;
}
for(int i=1;i<=n;i++) {
a[i].st=mp[a[i].st]--;
}
sort(a+1,a+1+n,[](ii a,ii b) {
if(a.nd<b.nd) return true;
if(a.nd>b.nd) return false;
return a.st>b.st;
});
//f(1,n,1,n);
for(int i=1;i<=n;i++) {
ans[i]=-inf;
for(int j=i;j>=1;j--) {
make(j,i);
if(i-j+1<m) continue ;
// cerr<<i<<" "<<j<<" "<<Maxm-2*(a[i].nd-a[j].nd)<<"\n";
umax(ans[i],Maxm-2*(a[i].nd-a[j].nd));
}
}
printf("%lld",*max_element(ans+1,ans+1+n));
}
