#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
#include <set>
#include <stdint.h>
const int64_t INF=1e15+7;
std::vector<std::pair<int64_t,int64_t> > cake;
int64_t N,M;
struct DataStruct{
std::multiset<int> low,high;
int64_t ll,rr;//(ll,rr) for elements, [ll,rr] for query
int64_t high_sum;
DataStruct():ll(0),rr(1),high_sum(0){
}
void up(){
high_sum+=*low.rbegin();
high.insert(*low.rbegin());
low.erase(low.find(*low.rbegin()));
}
void down(){
high_sum-=*high.begin();
low.insert(*high.begin());
high.erase(high.begin());
}
void balance(){
while(low.size()&&high.size()<M-2){
up();
}
while(high.size()>M-2){
down();
}
while(low.size()&&high.size()&&*low.rbegin()>*high.begin()){
up();
down();
}
}
void add(int64_t i){
int64_t x=cake[i].second;
low.insert(x);
}
void rem(int64_t i){
int64_t x=cake[i].second;
if(low.count(x)){
low.erase(low.find(x));
}else{
assert(high.count(x));
high_sum-=x;
high.erase(high.find(x));
}
}
int64_t query(int64_t l,int64_t r){
if(r-l+1<M) return -INF;
while(ll>l) add(ll--);
while(rr<r) add(rr++);
while(ll<l) rem(++ll);
while(rr>r) rem(--rr);
balance();
assert(high.size()+low.size()==r-l-1);
return high_sum+cake[l].second+cake[r].second+2LL*(cake[l].first-cake[r].first);
}
void dump(){
for(int64_t x:low) printf("%ld ",x);
printf("|");
for(int64_t x:high) printf(" %ld",x);
printf("\n");
}
}ds;
int64_t best=-INF;
//find ans for (l,r), which must be in range [low,high]
void solve(int64_t l,int64_t r,int64_t low,int64_t high){
if(r-l<=1) return;
int64_t m=(l+r)/2;
int64_t max=-INF;
int64_t maxi=-1;
for(int64_t i=low;i<=high;i++){
int64_t res=ds.query(m,i);
if(res>=max){
maxi=i;
max=res;
}
}
best=std::max(best,max);
//printf("best with l=%ld: %ld\n",m,max);
solve(l,m,low,maxi);
solve(m,r,maxi,high);
}
int64_t brute(int64_t l,int64_t r){
if(r-l+1<M) return -INF;
std::multiset<int> best;
for(int64_t i=l+1;i<r;i++){
best.insert(cake[i].second);
}
while(best.size()>M-2){
best.erase(best.begin());
}
assert(best.size()==M-2);
best.insert(cake[l].second);
best.insert(cake[r].second);
int64_t sum=2LL*(cake[l].first-cake[r].first);
for(int64_t x:best){
sum+=x;
}
return sum;
}
int main(){
scanf("%ld %ld",&N,&M);
for(int64_t i=0;i<N;i++){
int64_t V,C;
scanf("%ld %ld",&V,&C);
cake.push_back({C,V});
}
std::sort(cake.begin(),cake.end());
/*
for(int64_t l=0;l<N;l++){
for(int64_t r=0;r<N;r++){
printf("%ld,%ld ",ds.query(l,r),brute(l,r));
}
printf("\n");
}
*/
solve(-1,N,0,N-1);
/*
for(int64_t l=0;l<N;l++){
for(int64_t r=l;r<N;r++){
best=std::max(best,brute(l,r));
}
}
*/
printf("%ld\n",best);
//ds.query(0,N-1),ds.dump();
return 0;
}
