#include <iostream>
#include <algorithm>
#define f first
#define s second
using namespace std;
long long n, m, dp[2010][2010], maxx;
pair<long long,long long> a[200010];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i].s >> a[i].f;
sort(a+1,a+n+1);
for (int i = 1; i <= n; i++) dp[i][1] = a[i].s;
for (int k = 2; k <= m; k++) {
maxx = -1e18;
for (int i = 1; i <= n; i++) {
dp[i][k] = maxx-2*a[i].f+a[i].s;
maxx = max(maxx,dp[i][k-1]+2*a[i].f);
}
}
maxx = -1e18;
for (int i = 1; i <= n; i++) maxx = max(maxx,dp[i][m]);
cout << maxx << endl;
}
