#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;
vector<pair<int,int> > v;
int n,k;
int ans=-1e18;
vector<pair<int,int> > dp;
struct DS{
p_q<int,vector<int>,greater<int> > pq,pq2;
int cnt=0;
vector<int> v;
int sum=0;
void add(int x){
sum+=x;
cnt++;
v.push_back(x);
pq.push(x);
if(cnt>k){
pq2.push(pq.top());
sum-=pq.top();
v.push_back({-pq.top()});
cnt--;
}
while(pq.size() && pq2.size() && pq.top()==pq2.top()){
pq.pop();
pq2.pop();
}
}
void undo(){
while(v.back()<0){
auto h=-v.back();
v.pop_back();
pq.push(h);
cnt++;
sum+=h;
}
pq2.push(v.back());
sum-=v.back();
cnt--;
v.pop_back();
while(pq.size() && pq2.size() && pq.top()==pq2.top()){
pq.pop();
pq2.pop();
}
}
int get(){
return sum;
}
}ds;
void dc(int L,int R,int dl,int dr){
//cal dp[l] to dp[r], where their best transfer point will be in [dl,dr]
//the (dr,L) is given in ancestor
if(L>R){
return;
}
//cout << L << " " << R << " " << dl << " " << dr << "\n";
int m=(L+R)/2;
for(int i=m;i>=max(L,dr+1);i--){
ds.add(v[i].fs);
}
for(int i=min(dr,m);i>=dl;i--){
ds.add(v[i].fs);
if(m-i+1>=k){
cout << ds.get() << " " << v[m].sc-v[i].sc << "\n";
dp[m]=max(dp[m],{ds.get()-2*(v[m].sc-v[i].sc),i});
}
}
ans=max(ans,dp[m].fs);
for(int i=min(dr,m);i>=dl;i--){
ds.undo();
}
for(int i=m;i>=max(L,dr+1);i--){
ds.undo();
}
for(int i=dp[m].sc+1;i<=min(L-1,dr);i++){
ds.add(v[i].fs);
}
dc(L,m-1,dl,dp[m].sc);
for(int i=dp[m].sc+1;i<=min(L-1,dr);i++){
ds.undo();
}
for(int i=max(L,dr+1);i<=m;i++){
ds.add(v[i].fs);
}
dc(m+1,R,dp[m].sc,dr);
for(int i=max(L,dr+1);i<=m;i++){
ds.undo();
}
}
signed main(){
AquA;
cin >> n;
dp.resize(n,{-1e18,-1});
cin >> k;
v.resize(n);
for(int i=0;i<n;i++){
cin >> v[i].fs >> v[i].sc;
}
sort(v.begin(),v.end(),[&](pair<int,int> a,pair<int,int> b){return a.sc<b.sc;});
for(int i=0;i<n;i++){
//cout << v[i].fs << " " << v[i].sc << "\n";
}
dc(k,n-1,0,n-1);
for(int i=0;i<n;i++){
//cout << dp[i].fs << " " << dp[i].sc << "\n";
}
cout << ans << "\n";
return 0;
}
