#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 200000;
ll const inf = 1000000000000;
pair<int,int> v[1 + nmax];
pair<ll,int> _add(pair<ll,int> f1, pair<ll,int> f2){
return {f1.first + f2.first, f1.second + f2.second};
}
pair<ll,int> eval(int n, ll penal){
pair<ll,int> sol(v[1].second + penal, 1);
pair<ll,int> part(v[1].second + penal + 2 * v[1].first, 1);
for(int i = 2; i <= n; i++){
sol = max(sol, _add(part, {v[i].second + penal - 2 * v[i].first, 1}));
part = max(part, _add(part, {v[i].second + penal, 1}));
part = max(part, {v[i].second + penal + 2 * v[i].first, 1});
}
return sol;
}
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> v[i].second >> v[i].first;
sort(v + 1, v + n + 1);
ll penal = -inf;
for(ll jump = (1LL << 40); 0 < jump; jump /= 2){
if(eval(n, penal + jump).second < m)
penal += jump;
}
penal++;
pair<ll,int> sol = eval(n, penal);
cout << sol.first - 1LL * m * penal;
return 0;
}
