#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define all(x) (x).begin(),(x).end()
#define X first
#define Y second
#define sep ' '
#define endl '\n'
#define SZ(x) ll(x.size())
const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;
ll n , m , sum , curl = 1 , curr = 0 , V[MAXN] , C[MAXN] , ans[MAXN];
vector<pll> vec;
set<pll> st1;
set<pll , greater<pll>> st2;
void balance(){
while((SZ(st1) && SZ(st2) && (*st1.begin()) < (*st2.begin())) || SZ(st1) > m - 2){
sum -= (*st1.begin()).X;
st2.insert((*st1.begin()));
st1.erase(st1.begin());
}
while(SZ(st1) < m - 2 && 0 < SZ(st2)){
sum += (*st2.begin()).X;
st1.insert((*st2.begin()));
st2.erase(st2.begin());
}
}
void insert(int i){
st1.insert({V[i] , i}); sum += V[i];
balance();
// cout << "insert " << i << sep << sum << endl;
}
void remove(int i){
if(st1.find({V[i] , i}) != st1.end()){
st1.erase({V[i] , i}); sum -= V[i];
}
else{
st2.erase({V[i] , i});
}
balance();
// cout << "remove " << i << sep << sum << endl;
}
void move(int l , int r){
while(curr < r) insert(++curr);
while(l < curl) insert(--curl);
while(r < curr) remove(curr--);
while(curl < l) remove(curl++);
}
void solve(int l , int r , int optl , int optr){
if(r < l) return;
int mid = l + r >> 1 , opt = -1;
for(int i = optl ; i <= min(optr , mid - (int)m + 1) ; i++){
move(i + 1 , mid - 1);
// cout << i << sep << mid << sep << sum << endl;
if(sum + V[mid] + V[i] - C[mid] + C[i] > ans[mid]){
ans[mid] = sum + V[mid] - C[mid] + V[i] + C[i];
opt = i;
}
}
solve(l , mid - 1 , optl , opt);
solve(mid + 1 , r , opt , optr);
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
fill(ans , ans + MAXN , -INF);
cin >> n >> m;
for(int i = 1 ; i <= n ; i++){
cin >> V[i] >> C[i];
vec.push_back({C[i] , V[i]});
}
sort(all(vec));
for(int i = 1 ; i <= n ; i++){
C[i] = vec[i - 1].X * 2;
V[i] = vec[i - 1].Y;
}
solve(m , n , 1 , n);
ll res = -INF;
for(int i = 1 ; i <= n ; i++) res = max(res , ans[i]);
cout << res << endl;
return 0;
}
/*
*/
