#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 = 2e3+5;
vector< ii > vec;
int n, k;
int v[maxn];
int w[maxn];
ll bst[maxn][maxn];
struct node
{
int key, cnt, pr;
ll tot;
node *left, *right;
node(int key) : key(key)
{
tot = key;
cnt = 1;
pr = (rand()<<16)^rand();
left = right = NULL;
}
void calc()
{
tot = key;
if(left) tot += left->tot;
if(right) tot += right->tot;
cnt = 1+(left?left->cnt:0)+(right?right->cnt:0);
}
};
typedef node* ps;
ps merge(ps L, ps R)
{
if(!L || !R) return L?L:R;
if(L->pr> R->pr)
{
L->right = merge(L->right, R);
L->calc();
return L;
}
else
{
R->left = merge(L, R->left);
R->calc();
return R;
}
}
pair<ps, ps> splitsz(ps big, int key)
{
if(!big) return {big, big};
int here = 1+(big->left?big->left->cnt:0);
if(here<= key)
{
auto tmp = splitsz(big->right, key-here);
big->right = tmp.X;
big->calc();
return {big, tmp.Y};
}
else
{
auto tmp = splitsz(big->left, key);
big->left = tmp.Y;
big->calc();
return {tmp.X, big};
}
}
pair<ps, ps> split(ps big, int key)
{
if(!big) return {big, big};
int here = big->key;
if(here<= key)
{
auto tmp = split(big->right, key);
big->right = tmp.X;
big->calc();
return {big, tmp.Y};
}
else
{
auto tmp = split(big->left, key);
big->left = tmp.Y;
big->calc();
return {tmp.X, big};
}
}
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;
}
for(int i = 1; i<= n; i++)
{
ps root = NULL;
for(int j = i; j< (i+k-2)-1; j++)
{
auto tmp = split(root, v[j]);
ps r1 = merge(tmp.X, new node(v[j]));
root = merge(r1, tmp.Y);
}
for(int j = (i+k-2)-1; j<= n; j++)
{
auto tmp = split(root, v[j]);
ps r1 = merge(tmp.X, new node(v[j]));
root = merge(r1, tmp.Y);
int tot = (j-i+1);
tmp = splitsz(root, tot-(k-2));
// printf("left %d\n", tot-(k-2));
bst[i][j] = (tmp.Y)?(tmp.Y)->tot:0;
// printf("bst[%d][%d] = %lld\n", i, j, bst[i][j]);
root = merge(tmp.X, tmp.Y);
}
}
ll best = -1e18;
for(int i = 1; i<= n; i++)
{
for(int j = i+k-1; j<= n; j++)
{
best = max(best, bst[i+1][j-1]-2LL*(w[j]-w[i])+v[i]+v[j]);
}
}
printf("%lld\n", best);
}
