#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define ordered_set tree<pair<int, int>, null_type, greater<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update>
int ans[200005], n, m, l=-1, r=-1, sum, ANS;
vector<pair<int, int> > vec;
ordered_set s;
void add(int i)
{
s.insert({vec[i].second, i});
int ind=s.order_of_key({vec[i].second, i});
if (ind<m)
{
sum+=vec[i].second;
if (s.size()>m)
sum-=s.find_by_order(m)->first;
}
//cout << "add " << i << ' ' << sum << '\n';
}
void remove(int i)
{
s.erase({vec[i].second, i});
int ind=s.order_of_key({vec[i].second, i});
if (ind<m)
{
sum-=vec[i].second;
if (s.size()>=m)
sum+=s.find_by_order(m-1)->first;
}
//cout << "remove " << i << ' ' << sum << '\n';
}
void adjust(int ql, int qr)
{
//cout << "adjust " << l << ' ' << r << ' ' << ql << ' ' << qr << '\n';
if (r<ql || qr<l)
{
//cout << "reset " << ql << ' ' << qr << '\n';
l=ql, r=qr, sum=0, s.clear();
for (int i=l; i<=r; i++)
add(i);
return;
}
for (int i=l; i<ql; i++)
remove(i);
for (int i=ql; i<l; i++)
add(i);
for (int i=r+1; i<=qr; i++)
add(i);
for (int i=qr+1; i<=r; i++)
remove(i);
l=ql, r=qr;
}
void recur(int xl, int xr, int yl, int yr)
{
//cout << "recur " << xl << ' ' << xr << ' ' << yl << ' ' << yr << '\n';
int xmid=(xl+xr)/2, ind;
adjust(xmid+1, max(xmid+1, yl-1));
for (int i=max(xmid+2, yl); i<=yr; i++)
{
//cout << sum+vec[i].second-2*vec[i].first << '\n';
if (ans[xmid]<sum+vec[i].second-2*vec[i].first)
{
ans[xmid]=sum+vec[i].second-2*vec[i].first;
ind=i;
}
add(i);
r++;
}
if (xl<xmid)
recur(xl, xmid-1, yl, ind);
if (xmid<xr)
recur(xmid+1, xr, ind, yr);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
m-=2;
for (int i=0; i<n; i++)
{
int v, c;
cin >> v >> c;
vec.push_back({c, v});
}
sort(vec.begin(), vec.end());
for (int i=0; i<n; i++)
ans[i]=-1e18;
recur(0, n-m-2, m+1, n-1);
for (int i=0; i<n; i++)
ANS=max(ANS, ans[i]+vec[i].second+2*vec[i].first);
//for (int i=0; i<n; i++)
// cout << ans[i]+vec[i].second+2*vec[i].first << ' ';
//cout << '\n';
cout << ANS;
}
