/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 2e5 + 10;
int n, m;
pair < int, int > a[maxn];
void input()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
cin >> a[i].first >> a[i].second;
}
}
bool cmp_second(pair < int, int > f, pair < int, int > s)
{
return f.second < s.second;
}
ll inf = 1e18;
struct block
{
vector < ll > to_left, to_right;
void init(int idx)
{
to_left.resize(2);
to_right.resize(2);
to_left[0] = -inf;
to_left[1] = a[idx].first + 2 * a[idx].second;
to_right[0] = -inf;
to_right[1] = a[idx].first - 2 * a[idx].second;
}
};
block tree[4 * maxn];
ll result;
void conquer(int t, int l, int r)
{
int len = r - l + 1;
if (len >= m)
{
for (int i = 1; i <= m; i ++)
{
if (i < tree[t * 2].to_left.size() && m - i < tree[t * 2 + 1].to_right.size())
{
ll sum = tree[t * 2].to_left[i] + tree[t * 2 + 1].to_right[m - i];
if (sum > result)
{
//cout << l << " : " << r << " " << sum << endl;
result = sum;
}
}
}
}
vector < ll > lf_val, rf_val;
int mid = (l + r) / 2;
for (int i = l; i <= mid; i ++)
lf_val.push_back(a[i].first);
for (int i = mid + 1; i <= r; i ++)
rf_val.push_back(a[i].first);
sort(lf_val.begin(), lf_val.end());
reverse(lf_val.begin(), lf_val.end());
sort(rf_val.begin(), rf_val.end());
reverse(rf_val.begin(), rf_val.end());
lf_val.insert(lf_val.begin(), (ll)0);
rf_val.insert(rf_val.begin(), (ll)0);
for (int i = 1; i < lf_val.size(); i ++)
lf_val[i] += lf_val[i - 1];
for (int i = 1; i < rf_val.size(); i ++)
rf_val[i] += rf_val[i - 1];
tree[t].to_left.resize(r - l + 2, -inf);
for (int i = 1; i < tree[t * 2].to_left.size(); i ++)
tree[t].to_left[i] = max(tree[t].to_left[i], tree[t * 2].to_left[i]);
for (int i = 1; i < tree[t * 2 + 1].to_left.size(); i ++)
tree[t].to_left[i] = max(tree[t].to_left[i], tree[t * 2 + 1].to_left[i]);
//cout << "--------------------" << endl;
//cout << "range " << l << " " << r << endl;
for (int i = 1; i <= len; i ++)
{
for (int j = 1; j <= min((int)(tree[t * 2].to_left.size() - 1), i); j ++ )
{
if (i - j < rf_val.size())
tree[t].to_left[i] = max(tree[t].to_left[i], tree[t * 2].to_left[j] + rf_val[i - j]);
}
}
tree[t].to_right.resize(r - l + 2, -inf);
for (int i = 1; i < tree[t * 2].to_right.size(); i ++)
tree[t].to_right[i] = max(tree[t].to_right[i], tree[t * 2].to_right[i]);
for (int i = 1; i < tree[t * 2 + 1].to_right.size(); i ++)
tree[t].to_right[i] = max(tree[t].to_right[i], tree[t * 2 + 1].to_right[i]);
for (int i = 1; i <= len; i ++)
{
for (int j = 1; j <= min((int)tree[t * 2 + 1].to_right.size() - 1, i); j ++)
{
if (i - j < lf_val.size())
tree[t].to_right[i] = max(tree[t].to_right[i], tree[t * 2 + 1].to_right[j] + lf_val[i - j]);
}
}
//for (int i = 0; i < tree[t].to_left.size(); i ++)
// cout << tree[t].to_right[i] << " ";
//cout << endl;
}
void divide(int t, int l, int r)
{
if (l == r)
{
tree[t].init(l);
if (m == 1)
result = max(result, (ll)a[l].first);
return;
}
int mid = (l + r) / 2;
divide(t * 2, l, mid);
divide(t * 2 + 1, mid + 1, r);
conquer(t, l, r);
}
void do_math()
{
sort(a + 1, a + n + 1, cmp_second);
result = -inf;
divide(1, 1, n);
cout << result << endl;
}
void solve()
{
input();
do_math();
}
int main()
{
solve();
return 0;
}
