#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
#include <set>
#include <stdint.h>
#include <map>
const int64_t INF=1e15+7;
std::vector<std::pair<int,int> > cake;
std::map<int,int> cps;
int N,M;
const int MAXN=1<<18;
struct Node{
int cnt;
int64_t sum;
Node():cnt(0),sum(0){
}
}st[MAXN*2];
void st_add(int i,int c,int64_t v){
//printf("st_add(%d,%d,%ld)\n",i,c,v);
for(i+=MAXN;i>0;i>>=1){
st[i].cnt+=c;
st[i].sum+=v;
}
}
void st_insert(int x,int c){
//printf("st_insert(%d) x%d\n",x,c);
st_add(cps[x],c,x*c);
}
int64_t st_sum(int w,int L,int R,int k){
assert(st[w].cnt>=k);
if(st[w].cnt==k){
return st[w].sum;
}
int M=(L+R)/2;
if(st[w<<1|1].cnt>=k){
return st_sum(w<<1|1,M,R,k);
}else{
return st_sum(w<<1,L,M,k-st[w<<1|1].cnt)+st[w<<1|1].sum;
}
}
void st_dump();
int64_t st_sum(int k){
int64_t sum=0,cnt=0;
for(int i=MAXN-1;i>=0&&cnt<k;i--){
sum+=st[i+MAXN].sum;
cnt+=st[i+MAXN].cnt;
}
assert(cnt==k);
//st_dump();
//printf("st_sum(%d)=%ld\n",k,sum);
assert(sum==st_sum(1,0,MAXN,k));
return st_sum(1,0,MAXN,k);
}
void st_dump(){
for(int i=0;i<2*MAXN;i++){
if(st[i].cnt) printf(" ST[%d](%d): %ld\n",i,st[i].cnt,st[i].sum);
}
}
struct DataStruct{
std::multiset<int> low,high;
int ll,rr;//(ll,rr) for elements, [ll,rr] for query
int64_t high_sum;
DataStruct():ll(0),rr(1),high_sum(0){
}
void up(){
int x=*low.rbegin();
high_sum+=x;
high.insert(x);
low.erase(low.find(x));
}
void down(){
int x=*high.begin();
high_sum-=x;
low.insert(x);
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(int i){
st_insert(cake[i].second,1);
return;
int64_t x=cake[i].second;
low.insert(x);
}
void rem(int i){
st_insert(cake[i].second,-1);
return;
int64_t x=cake[i].second;
auto it=low.find(x);
if(it!=low.end()){
low.erase(it);
}else{
it=high.find(x);
assert(it!=high.end());
high_sum-=x;
high.erase(it);
}
}
int64_t query(int l,int 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);
return st_sum(M-2)+cake[l].second+cake[r].second;//+2LL*(cake[l].first-cake[r].first);
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(int l,int r,int low,int high){
if(r-l<=1) return;
int m=(l+r)/2;
int64_t max=-INF;
int maxi=-1;
for(int 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=0;//2LL*(cake[l].first-cake[r].first);
for(int64_t x:best){
sum+=x;
}
return sum;
}
int main(){
scanf("%d %d",&N,&M);
for(int i=0;i<N;i++){
int V,C;
scanf("%d %d",&V,&C);
cake.push_back({C,V});
cps[V];
}
{
int last=0;
for(auto& it:cps){
it.second=last++;
}
for(auto it:cps){
//printf("V=%d: %dyh\n",it.first,it.second);
}
}
std::sort(cake.begin(),cake.end());
/*
for(int l=0;l<N;l++){
for(int r=0;r<N;r++){
printf("%ld,%ld ",ds.query(l,r),brute(l,r));
}
printf("\n");
}
*/
solve(-1,N,0,N-1);
/*
for(int l=0;l<N;l++){
for(int 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;
}
