#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define int long long
const int N = 2e5 + 1;
const int inf = 1e9 + 7;
typedef pair<int,int> ii;
ii f[N];
ii T[N];
int n, m;
ii work(int M) {
ii cur = ii(0,0);
ii res = ii(0,0);
for(int i = 1 ; i <= n ; ++i) {
int B = cur.X + T[i].Y - 2 * T[i].X - M;
int C = cur.Y + 1;
if (C == 1)
B += 2 * T[i].X;
f[i] = ii(B,C);
cur = max(cur,ii(B + 2 * T[i].X,C));
res = max(res,ii(B,C));
}
return res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1 ; i <= n ; ++i)
cin >> T[i].Y >> T[i].X;
sort(T + 1,T + 1 + n);
int L = 0;
int R = inf;
while (L < R) {
int M = (L + R) / 2;
ii cur = work(M);
if (cur.Y <= m)
R = M;
else
L = M + 1;
}
ii res = work(L);
cout << res.X + L * m << endl;
}
/*
8 4
112103441 501365808
659752417 137957977
86280801 257419447
902409188 565237611
965602301 689654312
104535476 646977261
945132881 114821749
198700181 915994879
*/
