//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const ll INF = 1e16 + 7;
const int MAXN = 2e5 + 5;
const double eps = 1e-9;
pair<pii,int> a[MAXN];
ll ans = -INF;
int n, m, curL = 0, curR = -1;
pair<ll,int> seg[MAXN*4];
bool DEBUG = 0;
void upd(int l, int r, int k, int a, ll val) {
if (r < a || a < l) return;
if (a <= l && r <= a) {
if (val < 0)
seg[k] = {0, 0};
else
seg[k] = {val, 1};
return;
}
int mi = (l + r) / 2;
upd(l, mi, k*2, a, val);
upd(mi+1, r, k*2+1, a, val);
seg[k].fi = seg[k*2].fi + seg[k*2+1].fi;
seg[k].se = seg[k*2].se + seg[k*2+1].se;
if (DEBUG) {
//cerr<<"updseg: "<<l<<" "<<r<<" "<<seg[k].fi<<" "<<seg[k].se<<"\n";
}
}
pair<ll,int> qry(int l, int r, int k, int cnt) {
if (DEBUG) {
cerr<<"seg: "<<l<<" "<<r<<" "<<cnt<<" "<<seg[k].fi<<" "<<seg[k].se<<"\n";
}
if (seg[k].se <= cnt) return seg[k];
int mi = (l + r) / 2;
pair<ll,int> t1 = qry(mi+1, r, k*2+1, cnt);
if (t1.se >= cnt) return t1;
pair<ll,int> t2 = qry(l, mi, k*2, cnt - t1.se);
return mp(t1.fi+t2.fi, t1.se+t2.se);
}
ll qry(int lo, int hi) {
if (hi - lo + 1 < m)
return -INF;
while (curL > lo) {
curL--;
upd(0, n-1, 1, a[curL].se, a[curL].fi.se);
if (DEBUG) {
cerr<<"add "<<a[curL].fi.se<<"\n";
}
}
while (curR < hi) {
curR++;
upd(0, n-1, 1, a[curR].se, a[curR].fi.se);
if (DEBUG) {
cerr<<"add "<<a[curR].fi.se<<"\n";
}
}
while (curL < lo) {
upd(0, n-1, 1, a[curL].se, -1);
curL++;
if (DEBUG) {
cerr<<"remove "<<a[curL-1].fi.se<<"\n";
}
}
while (curR > hi) {
upd(0, n-1, 1, a[curR].se, -1);
curR--;
if (DEBUG) {
cerr<<"remove "<<a[curR+1].fi.se<<"\n";
}
}
upd(0, n-1, 1, a[lo].se, -1);
upd(0, n-1, 1, a[hi].se, -1);
ll ret = a[lo].fi.se + a[hi].fi.se - 2 * (a[hi].fi.fi - a[lo].fi.fi);
ll xa = qry(0, n-1, 1, m-2).fi;
ret = xa + a[lo].fi.se + a[hi].fi.se - 2 * (a[hi].fi.fi - a[lo].fi.fi);
if (DEBUG) {
cerr<<lo<<" "<<hi<<" "<<xa<<" "<<2 * (a[hi].fi.fi - a[lo].fi.fi)<<" "<<ret<<"\n";
}
upd(0, n-1, 1, a[lo].se, a[lo].fi.se);
upd(0, n-1, 1, a[hi].se, a[hi].fi.se);
//exit(0);
return ret;
}
void dfs(int l, int r, int oL, int oR) {
if (l > r) return;
int mi = (l + r) / 2, nx = oL;
ll val = -INF;
for (int i = max(oL, mi + m-1); i <= oR; i++) {
ll tmp = qry(mi, i);
if (tmp > val)
tie(nx, val) = mp(i, tmp);
}
ans = max(ans, val);
dfs(l, mi-1, oL, nx);
dfs(mi+1, r, nx, oR);
}
int main() {
assert(scanf("%d %d", &n, &m) == 2);
for (int i = 0; i < n; i++) {
assert(scanf("%d %d", &a[i].fi.fi, &a[i].fi.se) == 2);
a[i].se = 0;
}
sort(a, a + n);
for (int i = 0; i < n; i++) {
a[i].se = i;
swap(a[i].fi.fi, a[i].fi.se);
}
sort(a, a + n);
if (DEBUG) {
for (int i= 0; i < n; i++)
cerr<<a[i].fi.fi<<" "<<a[i].fi.se<<" "<<a[i].se<<"\n";
cerr<<"\n";
}
dfs(0, n-m, 0, n-1);
prl(ans);
return 0;
}
