#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
typedef double scal;
typedef vector<scal> poly;
const scal inf = 1e18;
#define MAX(x, y) ((x)>(y)?(x):(y))
__attribute__((optimize("O3,unroll-loops"),target("avx2,prefer-vector-width=128")))
void fast_mul(scal *__restrict dst, const scal *__restrict src1, const scal *__restrict src2, int n, int m)
{
int constexpr S = 128;
for (int l = 0; l < m; l += S) {
int r = min(l + S, m);
for (int i = 0; i < n; i++) {
for (int j = l; j < r; j++)
dst[i + j] = MAX(dst[i + j], src1[i] + src2[j]);
}
}
}
poly operator*(const poly &src1, const poly &src2)
{
poly ans(src1.size() + src2.size() - 1, -inf);
fast_mul(ans.data(), src1.data(), src2.data(), src1.size(), src2.size());
return ans;
}
poly operator+(const poly &src1, const poly &src2)
{
bool swp = src1.size() < src2.size();
auto &a = swp? src2: src1;
auto &b = swp? src1: src2;
poly ans(a.size());
Loop (i,0,b.size())
ans[i] = MAX(a[i], b[i]);
Loop (i,b.size(),a.size())
ans[i] = a[i];
return ans;
}
const int N = 200'010;
pair<scal, scal> arr[N];
int n, M;
scal ans = -inf;
void solve(int l, int r, poly *pl, poly *pm, poly *pr)
{
if (r - l == 1) {
if (pl) *pl = { -inf, arr[l].second + 2 * arr[l].first };
if (pm) *pm = { 0, arr[l].second};
if (pr) *pr = { -inf, arr[l].second - 2 * arr[l].first };
return;
}
int m = (l + r)/2;
poly Pll, Plm, Plr;
poly Prl, Prm, Prr;
solve(l, m, &Pll, pr || pm? &Plm: nullptr, pr? &Plr: nullptr);
solve(m, r, pl? &Prl: nullptr, pl || pm? &Prm: nullptr, &Prr);
if (r - l >= M) {
Loop (i,0,M+1) {
if (Pll.size() > i && Prr.size() > M-i)
ans = max(ans, Pll[i] + Prr[M-i]);
}
}
if (pm) *pm = Plm * Prm;
if (pl) *pl = Pll * Prm + Prl;
if (pr) *pr = Prr * Plm + Plr;
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n >> M;
Loop (i,0,n) {
ll v, c;
cin >> v >> c;
arr[i].first = c;
arr[i].second = v;
}
sort(arr, arr+n);
solve(0, n, nullptr, nullptr, nullptr);
cout << (ll)ans << '\n';
}
