#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
typedef long long llong;
const int MAXN = 200000 + 10;
const llong INF = 1e18;
int n, k;
int v[MAXN];
int c[MAXN];
int sortedV[MAXN];
struct SegmentTree
{
struct Node
{
llong sum;
int cnt;
Node()
{
sum = cnt = 0;
}
friend Node operator + (const Node &left, const Node &right)
{
Node res;
res.sum = left.sum + right.sum;
res.cnt = left.cnt + right.cnt;
return res;
}
};
Node tree[4*MAXN];
void update(int l, int r, int node, int queryPos)
{
if (l == r)
{
if (tree[node].cnt == 1)
{
tree[node].sum = 0;
tree[node].cnt = 0;
} else
{
tree[node].sum = sortedV[l];
tree[node].cnt = 1;
}
return;
}
int mid = (l + r) / 2;
if (queryPos <= mid) update(l, mid, 2*node, queryPos);
else update(mid + 1, r, 2*node + 1, queryPos);
tree[node] = tree[2*node] + tree[2*node + 1];
}
int findPos(int l, int r, int node, int k)
{
if (l == r)
{
return l;
}
int mid = (l + r) / 2;
if (tree[2*node].cnt >= k)
{
return findPos(l, mid, 2*node, k);
} else
{
return findPos(mid + 1, r, 2*node + 1, k - tree[2*node].cnt);
}
}
llong query(int l, int r, int node, int queryL, int queryR)
{
if (queryL <= l && r <= queryR)
{
return tree[node].sum;
}
llong res = 0;
int mid = (l + r) / 2;
if (queryL <= mid) res += query(l, mid, 2*node, queryL, queryR);
if (mid + 1 <= queryR) res += query(mid + 1, r, 2*node + 1, queryL, queryR);
return res;
}
void update(int pos)
{
update(1, n, 1, pos);
}
llong query()
{
int to = findPos(1, n, 1, k);
return query(1, n, 1, 1, to);
}
};
int inOrder[MAXN];
int revOrder[MAXN];
std::pair <int,int> toSort[MAXN];
SegmentTree tree;
int ptrL = 1;
int ptrR = 0;
llong cost(int l, int r)
{
r--;
l++;
while (ptrL < l)
{
tree.update(revOrder[ptrL]);
ptrL++;
}
while (ptrL > l)
{
ptrL--;
tree.update(revOrder[ptrL]);
}
while (ptrR > r)
{
tree.update(revOrder[ptrR]);
ptrR--;
}
while (ptrR < r)
{
ptrR++;
tree.update(revOrder[ptrR]);
}
return tree.query() + v[l - 1] + v[r + 1] - 2 * (c[r + 1] - c[l - 1]);
}
llong ans = -INF;
void divide(int l, int r, int optL, int optR)
{
int opt = -1;
llong curr = -INF;
int mid = (l + r) / 2;
for (int i = std::max(mid + k + 1, optL) ; i <= optR ; ++i)
{
llong res = cost(mid, i);
if (res > curr)
{
curr = res;
opt = i;
}
}
ans = std::max(ans, curr);
if (l < mid) divide(l, mid - 1, optL, opt);
if (mid < r) divide(mid + 1, r, opt, optR);
}
void solve()
{
std::sort(toSort + 1, toSort + 1 + n);
for (int i = 1 ; i <= n ; ++i)
{
c[i] = toSort[i].first;
v[i] = toSort[i].second;
}
std::iota(inOrder + 1, inOrder + 1 + n, 1);
std::sort(inOrder + 1, inOrder + 1 + n, [&](int x, int y)
{
return v[x] > v[y];
});
for (int i = 1 ; i <= n ; ++i)
{
sortedV[i] = v[inOrder[i]];
revOrder[inOrder[i]] = i;
}
k -= 2;
divide(1, n - k - 1, 1, n);
std::cout << ans << '\n';
}
void input()
{
std::cin >> n >> k;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> toSort[i].second >> toSort[i].first;
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
