#include <bits/stdc++.h>
using namespace std;
#define db(...) " [" << #__VA_ARGS__ << " : " << (__VA_ARGS__) << "] "
const int N = 200005;
const int LOG = 17;
#define MASK(x) (1LL << (x))
template<class T>
struct fenwick_tree {
T s[N];
void update(int i, T x) {
for (; i <= 200000; i += i & -i) {
s[i] += x;
}
}
T get(int i) {
T res = 0;
for (; i > 0; i -= i & -i) {
res += s[i];
}
return res;
}
T get(int l, int r) {
return get(r) - get(l - 1);
}
int lower_bound(T k) {
int x = 0;
for (int i = MASK(LOG); i; i >>= 1) {
if (x + i <= 200000 && k >= s[x + i]) {
x += i;
k -= s[x];
}
}
return x;
}
};
struct T {
int v, c;
T() {};
T(int v, int c): v(v), c(c) {};
bool operator < (const T &oth) const {
return c < oth.c;
}
void read() {
cin >> v >> c;
}
} a[N];
int n, m;
int k;
vector<int> values;
int val(int idx) {
return values[k - idx];
}
int L = 1, R = 0;
fenwick_tree<long long> ft;
fenwick_tree<int> num;
long long get() {
int cnt = m - 2;
int pos = num.lower_bound(cnt - 1) + 1;
long long res = ft.get(pos - 1);
cnt -= num.get(pos - 1);
res += 1LL * val(pos) * cnt;
return res;
}
long long res = -1e18;
void add(int i) {
if (i) {
num.update(a[i].v, 1);
ft.update(a[i].v, val(a[i].v));
}
}
void del(int i) {
if (i) {
num.update(a[i].v, -1);
ft.update(a[i].v, -val(a[i].v));
}
}
void dnc(int l, int r, int optl, int optr) {
if (l > r) {
return;
}
int mid = l + r >> 1;
while (L > mid + 1) add(--L);
while (R < optr) add(++R);
while (L < mid + 1) del(L++);
while (R > optr) del(R--);
pair<long long, int> best = {-1e18, -1};
for (int i = optr; i >= max(mid + m - 1, optl); --i) {
while (R > i - 1) del(R--);
long long cost = -2LL * (a[i].c - a[mid].c);
cost += val(a[i].v);
cost += val(a[mid].v);
cost += get();
if (cost > best.first) {
best.first = cost;
best.second = i;
}
}
assert(best.second != -1);
res = max(res, best.first);
dnc(l, mid - 1, optl, best.second);
dnc(mid + 1, r, best.second, optr);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
a[i].read();
values.emplace_back(a[i].v);
}
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
k = values.size();
for (int i = 1; i <= n; ++i) {
a[i].v = lower_bound(values.begin(), values.end(), a[i].v) - values.begin() + 1;
a[i].v = k - a[i].v + 1;
}
sort(a + 1, a + n + 1);
dnc(1, n - m + 1, m, n);
cout << res;
}
