// ~Be name khoda~ //
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define cl clear
#define endll '\n'
const int maxn = 1e6 + 10;
const int maxn5 = 2e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 2e18;
int n, m, curl, curr;
int v[maxn5], c[maxn5];
int per[maxn5], tc[maxn5];
int tv[maxn5];
ll cost = 0, out;
//vector <int> av;
multiset <int> mx, mn;
inline bool cmp(int i, int j){return c[i] < c[j];}
inline void add(int id){
//cout << "adding " << id << endl;
//cout << "______________ " << (*mx.begin()) << endl;
if(mx.size() < m - 2){
mx.insert(v[id]);
cost += v[id];
//cout << "to mx" << endl;
return;
}
if((*mx.begin()) < v[id]){
mn.insert((*mx.begin()) * -1);
//cout << "por " << (*mx.begin()) << endl;
cost -= (*mx.begin());
mx.erase(mx.begin());
mx.insert(v[id]);
cost += v[id];
//cout << "to mx with erasing!" << endl;
return;
}
mn.insert(-v[id]);
//cout << "to mn " << id << endl;
return;
}
inline void remo(int id){
//cout << "removing " << id << endl;
if((*mx.begin()) <= v[id]){
//cout << "form mx << endl" << endl;
//cout << "noo " << v[id] << ' ' << id << ' ' << curl << ' ' << curr << endl;
mx.erase(mx.find(v[id]));
cost -= v[id];
if(!mn.empty()){
mx.insert((*mn.begin()) * -1);
cost -= (*mn.begin());
//cout << "wow " << (*mn.begin()) << endl;
mn.erase(mn.begin());
}
}
else{
//cout << "from mn " << endl;
//cout << "em no " << ' ' << curl << ' ' << curr << ' ' << id << endl;
//cout << "so right " << id << endl;
mn.erase(mn.find(-v[id]));
}
return;
}
inline void calc(int l, int r){
/*
av.clear();
for(int i = l; i <= r; i++)
av.pb(v[i]);
sort(all(av));
cost = av.back() + av[av.size() - 2];
return;
*/
while(curr < r){
curr++;
add(curr);
}
while(curl > l){
curl--;
add(curl);
}
while(curr > r){
remo(curr);
curr--;
}
while(curl < l){
remo(curl);
curl++;
}
return;
}
inline void solve(int l, int r, int opl, int opr){
if(l >= r)
return;
int mid = (l + r) >> 1;
int opt = -1;
ll ans = -1 * inf;
//cout << l << ' ' << r << ' ' << opl << ' ' << opr << endl;
for(int i = opl; i < min(mid - m + 2, opr); i++){
calc(i + 1, mid - 1);
//cout << i << ' ' << mid << ' ' << cost << endl;
ll val = 2 * c[i] + cost - 2 * c[mid] + v[i] + v[mid];
if(ans <= val){
ans = val;
opt = i;
}
}
out = max(out, ans);
if(r - l == 1)
return;
solve(l, mid, opl, opt + 1);
solve(mid + 1, r, opt, opr);
return;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 0; i < n; i++){
cin >> v[i] >> c[i];
per[i] = i;
}
sort(per, per + n, cmp);
for(int i = 0; i < n; i++){
tv[i] = v[per[i]];
tc[i] = c[per[i]];
}
for(int i = 0; i < n;i ++){
v[i] = tv[i];
c[i] = tc[i];
}
out = -1 * inf;
curl = m - 1;
curr = m - 1;
mx.insert(v[m - 1]);
cost = v[m - 1];
solve(m - 1, n, 0, n);
cout << out << endl;
}
