#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 2e5+5;
vector< ii > vec;
int n, k;
int v[maxn];
int w[maxn];
struct node
{
ll sum;
int left, right;
node(){}
node(ll val, int left, int right) : sum(val), left(left), right(right){}
};
node cnt[20*maxn], tot[20*maxn];
int tungc = 0;
int tungd = 0;
int pos[maxn];
int rcnt[maxn], rtot[maxn];
int update(node *st, int &tung, int x, int dx, int p, int L, int R)
{
if(L<= x && x<= R)
{
if(L == R)
{
tung++;
st[tung] = node(st[p].sum+dx, 0, 0);
return tung;
}
int M = (L+R)/2;
int a = update(st, tung, x, dx, st[p].left, L, M);
int b = update(st, tung, x, dx, st[p].right, M+1, R);
tung++;
st[tung] = node(st[a].sum+st[b].sum, a, b);
return tung;
}
return p;
}
ll gimme(int p1, int p2, int p3, int p4, ll k, int L, int R)
{
if(L == R)
{
// printf("end at %d %lld\n", L, k);
if(k> 0) return tot[p4].sum-tot[p3].sum;
return 0;
}
int M = (L+R)/2;
ll here = (cnt[cnt[p2].right].sum)-(cnt[cnt[p1].right].sum);
// printf("%d %d right = %lld all %lld\n", L, R, here, cnt[p2].sum-cnt[p1].sum);
// printf("from %lld+%lld\n", cnt[cnt[p2].left].sum-cnt[cnt[p1].left].sum, cnt[cnt[p2].right].sum-cnt[cnt[p1].right].sum);
if(here>= k)
{
return gimme(cnt[p1].right, cnt[p2].right, tot[p3].right, tot[p4].right, k, M+1, R);
}
else
{
// printf("adding %lld\n", tot[tot[p4].right].sum-tot[tot[p3].right].sum);
return (tot[tot[p4].right].sum)-(tot[tot[p3].right].sum)+gimme(cnt[p1].left, cnt[p2].left, tot[p3].left, tot[p4].left, k-here, L, M);
}
}
ll cost(int x, int y)
{
// printf("querying %d %d\n", x, y);
return gimme(rcnt[x-1], rcnt[y], rtot[x-1], rtot[y], k-2, 1, n);
}
ll ret = -1e18;
void solve(int L, int R, int i, int j)
{
if(L> R) return;
int M = (L+R)/2;
pair<ll, int> best = {-1e18, i};
for(int p = 1; p<= M-2; p++)
{
//[p..M]
// printf("cost[%d..%d] = %lld\n", p+1, M-1, cost(p+1, M-1));
best = max(best, {cost(p+1, M-1)+v[M]+v[p]-2LL*(w[M]-w[p]), p});
}
ret = max(ret, best.X);
solve(L, M-1, i, best.Y);
solve(M+1, R, best.Y, j);
}
int main()
{
scanf("%d %d", &n, &k);
vec.resize(n);
for(int i = 0; i< n; i++)
{
scanf("%d %d", &vec[i].Y, &vec[i].X);
}
sort(vec.begin(), vec.end());
for(int i = 1; i<= n; i++)
{
v[i] = vec[i-1].Y;
w[i] = vec[i-1].X;
}
cnt[0].sum = tot[0].sum = 0;
cnt[0].left = cnt[0].right = 0;
tot[0].left = tot[0].right = 0;
vector< ii > ayh;
for(int i = 1; i<= n; i++)
{
ayh.pb(ii(v[i], i));
}
sort(ayh.begin(), ayh.end());
for(int i = 0; i< n; i++)
{
pos[ayh[i].Y] = i+1;
}
// for(int i = 1; i<= n; i++) printf("%d %d\n", v[i], w[i]);
for(int i = 1; i<= n; i++)
{
// printf("updating %d\n", pos[i]);
rcnt[i] = update(cnt, tungc, pos[i], 1, rcnt[i-1], 1, n);
rtot[i] = update(tot, tungd, pos[i], v[i], rtot[i-1], 1, n);
}
// printf("done\n");
solve(1, n, 1, n);
// for(int i = 1; i<= n; i++)
// {
// for(int j = i+k-1; j<= n; j++)
// {
// ret = max(ret, cost(i+1, j-1)+v[i]+v[j]-2LL*(w[j]-w[i]));
// }
// }
printf("%lld\n", ret);
}
