#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
using ll = long long;
using pii = pair<ll, ll>;
const ll maxn = 4e6 + 5, inf = 1e9, oo = 1e18;
ll n, m, dp[2][maxn];
pii a[maxn];
struct WT
{
struct node
{
int l, r;
vector<ll> x;
vector<ll> s;
} t[maxn];
int build(vector<ll> &seq, ll a = 0, ll b = inf)
{
static int idxNode = 0;
if (seq.empty())
return -1;
int cur = idxNode++;
if (a == b)
return cur;
t[cur].x.resize(seq.size());
t[cur].s.resize(seq.size());
ll mid = (a + b) / 2;
vector<ll> left_seq, right_seq;
for (int i = 0; i < (int)seq.size(); i++)
{
if (seq[i] <= mid)
{
left_seq.push_back(seq[i]);
}
else
{
t[cur].x[i] = 1;
t[cur].s[i] = seq[i];
right_seq.push_back(seq[i]);
}
}
for (int i = (int)seq.size() - 2; i >= 0; i--)
{
t[cur].x[i] += t[cur].x[i + 1];
t[cur].s[i] += t[cur].s[i + 1];
}
t[cur].l = build(left_seq, a, mid);
t[cur].r = build(right_seq, mid + 1, b);
return cur;
}
int map_left(int nd, int i)
{
return i >= 0 ? i - t[nd].x[i] : -1;
}
int map_right(int nd, int i)
{
return i >= 0 ? t[nd].x[i] - 1 : -1;
}
int countRight(int cur, int l, int r)
{
if (l > r)
return 0;
ll totalR = t[cur].x[l];
ll beyond = (r + 1 < (int)t[cur].x.size()) ? t[cur].x[r + 1] : 0;
return (int)(totalR - beyond);
}
int64_t sumRight(int cur, int l, int r)
{
if (l > r)
return 0LL;
ll totalR = t[cur].s[l];
ll beyond = (r + 1 < (int)t[cur].s.size()) ? t[cur].s[r + 1] : 0LL;
return (totalR - beyond);
}
ll queryUtil(int node, int a, int b, int l, int r, int k)
{
if (node == -1 || l > r || k <= 0)
return 0LL;
if (a == b)
{
int countSeg = (r - l + 1);
int take = min(countSeg, k);
return 1LL * take * a;
}
int mid = (a + b) >> 1;
int totalR = countRight(node, l, r);
if (totalR >= k)
{
int newL = map_right(node, l - 1) + 1;
int newR = map_right(node, r);
return queryUtil(t[node].r, mid + 1, b, newL, newR, k);
}
else
{
ll sumR = sumRight(node, l, r);
int newL = map_left(node, l - 1) + 1;
int newR = map_left(node, r);
return sumR + queryUtil(t[node].l, a, mid, newL, newR, k - totalR);
}
}
ll query(int l, int r, int k)
{
if (l > r)
return 0LL;
return queryUtil(0, 0, inf, l, r, k);
}
} tree;
void calc(int x, int l, int r, int opl, int opr)
{
if (l > r)
return;
int mid = l + r >> 1;
pii best = {-oo, -1};
for (int k = opl; k < min(mid, opr); k++)
{
best = max(best, {tree.query(k + 1, mid - 1, m - 2) + a[mid].fi + a[k].fi - 2 * abs(a[mid].se - a[k].se), k});
}
dp[x][mid] = best.fi;
int opt = best.se;
calc(x, l, mid - 1, opl, opt);
calc(x, mid + 1, r, opt, opr);
}
vector<ll> b;
signed main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> a[i].fi >> a[i].se;
}
sort(a, a + n, [](auto x, auto y)
{ return x.se < y.se; });
for (int i = 0; i < n; i++)
{
dp[0][i] = a[i].fi - a[i].se;
b.push_back(a[i].fi);
}
tree.build(b);
calc(1, 0, n - 1, 0, n - 1);
cout << *max_element(dp[1], dp[1] + n);
return 0;
}
