#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 = 4000005, inf = 1000000000, oo = 1000000000000000000LL;
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++;
t[cur].x.assign(seq.size(), 0);
t[cur].s.assign(seq.size(), 0);
if (A == B)
return cur;
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);
}
ll 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;
vector<ll> b;
void calc(int x, int l, int r, int opl, int opr)
{
stack<tuple<int, int, int, int>> st;
st.push({l, r, opl, opr});
while (!st.empty())
{
auto [L, R, opL, opR] = st.top();
st.pop();
if (L > R)
continue;
int mid = (L + R) >> 1;
pii best = {-oo, -1};
int limit = min(mid - 1, opR);
for (int k = opL; k <= limit; k++)
{
ll candidate = tree.query(k + 1, mid - 1, m - 2) + a[mid].fi + a[k].fi - 2 * abs(a[mid].se - a[k].se);
best = max(best, {candidate, k});
}
dp[x][mid] = best.fi;
int opt = best.se;
st.push({L, mid - 1, opL, opt});
st.push({mid + 1, R, opt, opR});
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> a[i].fi >> a[i].se;
}
sort(a, a + n, [](const pii &x, const pii &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;
}
