#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42;
int n,m;
pair<int/*v*/,int/*c*/> inp[nmax];
bool cmp(pair<int/*v*/,int/*c*/> a,pair<int/*v*/,int/*c*/> b)
{
return a.second<b.second;
}
int in=0;
long long sum_in=0,sum_greatest=-1e18;
set< pair<int/*value*/,int/*position*/> > active;
set< pair<int/*value*/,int/*position*/> >::iterator it;
void to_add(int positon)
{
pair<int/*value*/,int/*position*/> current={inp[positon].first,positon};
in++;
sum_in+=current.first;
if(in<=m)
{
active.insert(current);
if(in==m)
{
sum_greatest=sum_in;
it=active.begin();
}
}
else
{
if(current<(*it))//current is less than the greatest m values
{
active.insert(current);
}
else//current is greater than some of the greatest m values
{
sum_greatest-=(*it).first;
active.insert(current);
sum_greatest+=current.first;
it++;
}
}
}
void to_remove(int positon)
{
pair<int/*value*/,int/*position*/> current={inp[positon].first,positon};
in--;
sum_in-=current.first;
if(in<m)sum_greatest=-1e18;
if(in>=m)
{
if(current<(*it))//current is less than the greatest m values
{
active.erase(current);
}
else//current is greater than some of the greatest m values
{
sum_greatest-=(current).first;
it--;
active.erase(current);
sum_greatest+=(*it).first;
}
}
else
{
active.erase(current);
}
}
long long output=-1e18;
int left_pointer=1,right_pointer=0;
void make_active(int l,int r)
{
l++;
r--;
while(left_pointer>l)
{
left_pointer--;
to_add(left_pointer);
}
while(right_pointer<r)
{
right_pointer++;
to_add(right_pointer);
}
while(left_pointer<l)
{
to_remove(left_pointer);
left_pointer++;
}
while(right_pointer>r)
{
to_remove(right_pointer);
right_pointer--;
}
}
void divide_and_conquer(int l,int r,int answer_left,int answer_right)
{
if(l>r)return;
int av=(l+r)/2;
int best_position=answer_left;
long long best_answer=-1e18;
for(int j=answer_left;j<=answer_right&&j<av;j++)
{
make_active(j,av);
long long current=inp[av].first+inp[j].first-2*(inp[av].second-inp[j].second);
if(in<m)current=-1e18;
else current+=sum_greatest;
if(best_answer<current)
{
best_answer=current;
best_position=j;
}
//cout<<j<<" "<<av<<" -> "<<in<<" "<<sum_in<<" "<<sum_greatest<<" "<<current<<endl;
output=max(output,current);
}
divide_and_conquer(l,av-1,answer_left,best_position);
divide_and_conquer(av+1,r,best_position,answer_right);
}
int main()
{
scanf("%i%i",&n,&m);
m=m-2;
for(int i=1;i<=n;i++)scanf("%i%i",&inp[i].first,&inp[i].second);
sort(inp+1,inp+n+1,cmp);
it=active.begin();
divide_and_conquer(1,n,1,n);
printf("%lld\n",output);
return 0;
}
