#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;
typedef long long ll;
const ll INF = 1e18;
vector<ll> Vcmp;
ll getIdx(ll x, vector<ll> &v){
return lower_bound(v.begin(), v.end(), x) - v.begin();
}
struct Node{
ll l=-1,r=-1;
ll cnt=0,sum=0;
};
struct PersistentTree{
public:
ll N;
vector<ll> root;
vector<Node> tree;
PersistentTree(ll n){
N = n;
root.push_back(0);
tree.push_back({-1,-1,0,0});
build(0, 0, N-1);
}
void update(ll idx){
root.push_back(tree.size());
tree.push_back({-1,-1,0,0});
update(root.back(), 0, N-1, idx, root[root.size()-2]);
}
ll query(ll i, ll j, ll x){
if(tree[root[j]].cnt - tree[root[i-1]].cnt < x) return -INF;
return query(root[i-1], root[j], 0, N-1, x);
}
private:
void build(ll node, ll st, ll en){
if(st == en) return;
ll mid = (st + en)/2;
tree[node].l = tree.size();
tree.push_back({-1,-1,0,0});
build(tree[node].l, st, mid);
tree[node].r = tree.size();
tree.push_back({-1,-1,0,0});
build(tree[node].r, mid+1, en);
}
void update(ll node, ll st, ll en, ll idx, ll prv){
if(prv != -1) tree[node] = tree[prv];
if(st == en) {
tree[node].cnt ++;
tree[node].sum += Vcmp[idx];
} else {
ll mid = (st + en)/2;
if(idx <= mid){
tree[node].l = tree.size();
tree.push_back({-1,-1,0,0});
update(tree[node].l, st, mid, idx, (prv==-1?-1:tree[prv].l));
} else {
tree[node].r = tree.size();
tree.push_back({-1,-1,0,0});
update(tree[node].r, mid+1, en, idx, (prv==-1?-1:tree[prv].r));
}
tree[node].cnt = tree[tree[node].l].cnt+tree[tree[node].r].cnt;
tree[node].sum = tree[tree[node].l].sum+tree[tree[node].r].sum;
}
}
ll query(ll i, ll j, ll st, ll en, ll x){
if(st == en) return x*Vcmp[st];
ll mid = (st + en)/2;
if(tree[j].cnt-tree[i].cnt == x) return tree[j].sum - tree[i].sum;
ll rcnt = tree[tree[j].r].cnt - tree[tree[i].r].cnt;
ll rsum = tree[tree[j].r].sum - tree[tree[i].r].sum;
if(x <= rcnt) return query(tree[i].r, tree[j].r, mid+1, en, x);
return rsum + query(tree[i].l, tree[j].l, st, mid, x-rcnt);
}
};
ll N,M;
vector<ll> dp,opt;
vector<pair<ll,ll>> VC;
void dnc(ll st, ll en, ll p, ll q, PersistentTree &PST){
if(st > en) return;
if(p == q){
for(ll i=st;i<=en;i++){
dp[i] = 2*(VC[i-1].second-VC[p-1].second) + PST.query(i+1, p-1, M-2) + Vcmp[VC[i-1].first] + Vcmp[VC[p-1].first];
opt[i] = p;
}
} else {
ll mid = (st + en)/2;
for(ll i=max(p,mid+M-1);i<=q;i++){
ll tmp = 2*(VC[mid-1].second - VC[i-1].second) + PST.query(mid+1, i-1, M-2) + Vcmp[VC[mid-1].first] + Vcmp[VC[i-1].first];
if(dp[mid] < tmp){
opt[mid] = i;
dp[mid] = tmp;
}
}
dnc(st, mid-1, p, opt[mid], PST), dnc(mid+1, en, opt[mid], q, PST);
}
}
int main(){
fastio;
cin >> N >> M;
VC.resize(N);
for(auto &[v,c] : VC) cin >> v >> c, Vcmp.push_back(v);
sort(VC.begin(), VC.end(), [&](const pair<ll,ll> &p1, const pair<ll,ll> &p2){
return p1.second < p2.second;
});
sort(Vcmp.begin(), Vcmp.end());
Vcmp.erase(unique(Vcmp.begin(), Vcmp.end()), Vcmp.end());
for(auto &[v,c] : VC) v = getIdx(v, Vcmp);
dp.resize(N-M+10,-INF); opt.resize(N-M+10,-1);
PersistentTree PST(N+10);
for(ll i=1;i<=N;i++) PST.update(VC[i-1].first);
dnc(1, N-M+1, 1, N, PST);
// for(int i=1;i<=N-M+1;i++) cout << opt[i] << " ";
// cout << '\n';
cout << *max_element(dp.begin(), dp.end());
// cout << "\n";
// cout << PST.query(6, 7, 2);
}
