#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
void ngha();
const int mod2 = 1e9 + 7;
const int mod1 = 998244353;
struct ib
{
int a;
int b;
};
struct icd
{
int a, b;
};
struct ic
{
int a, b, c;
};
struct id
{
int a, b, c, d;
};
struct ie
{
int a, b, c, d, e;
};
int n, m, s1, s2, s4, s3, sf, k, r, mid, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, l;
int i, s10, s12;
int el = 29;
main()
{
//#ifndef ONLINE_JUDGE
// fin(task),fou(task);
//#endif
NHP
//modwwe
// cin>>res;
ngha(), down
checktime
}
bool cmp(ib a, ib b)
{
return a.b < b.b;
}
vector<int> v;
ic t[800001];
ib t2[800001];
ib a[2000001];
void build(int node, int l, int r)
{
t[node].c = n + 1;
if(l == r)
return;
int mid = l + r >> 1;
build(node << 1, l, mid);
build(node << 1 | 1, mid + 1, r);
}
void upd(int node, int l, int r, int l1, int r1, int x)
{
if(l > r1 || r < l1)
return;
if(l >= l1 && r <= r1)
{
t[node].b += x;
t[node].a = t[node].b * v[l-1];
if(t[node].b == 0)
t[node].c = n + 1;
else
t[node].c = l;
return;
}
int mid = l + r >> 1;
upd(node << 1, l, mid, l1, r1, x);
upd(node << 1 | 1, mid + 1, r, l1, r1, x);
t[node].c = min(t[node << 1].c, t[node << 1 | 1].c);
t[node].b = t[node << 1].b + t[node << 1 | 1].b;
t[node].a = t[node << 1].a + t[node << 1 | 1].a;
}
void upd2(int node, int l, int r, int l1, int r1, int x)
{
if(l > r1 || r < l1)
return;
if(l >= l1 && r <= r1)
{
t2[node].b += x;
if(t2[node].b != 0)
t2[node].a = l;
else
t2[node].a = 0;
return;
}
int mid = l + r >> 1;
upd2(node << 1, l, mid, l1, r1, x);
upd2(node << 1 | 1, mid + 1, r, l1, r1, x) ;
t2[node].a = max(t2[node << 1].a, t2[node << 1 | 1].a);
}
void del(int f)
{
if(t[1].c <= f)
{
upd(1, 1, n, f, f, -1);
if(t2[1].a > 0)
{
upd(1, 1, n, t2[1].a, t2[1].a, 1);
upd2(1, 1, n, t2[1].a, t2[1].a, -1);
}
}
else
{
upd2(1, 1, n, f, f, -1);
}
}
/// a be nhat
void ff(int f)
{
if(t[1].b < m){
upd(1, 1, n, f, f, 1);
return;}
else if(t[1].c < f)
{int sss=t[1].c;
upd(1, 1, n, f, f, 1);
upd2(1, 1, n, sss, sss, 1);
upd(1, 1, n, sss, sss, -1);
return;
}
else
{
upd2(1, 1, n, f, f, 1);
return;
}
}
void up(int x, int y)
{
while(l > x)
{
l--;
ff(a[l].a);
}
while(r < y)
{
r++;
ff(a[r].a);
}
while(r > y)
{
del(a[r].a);
r--;
}
while(l < x)
{
del(a[l].a);
l++;
}
}
void calc(int x, int y, int l2, int r2)
{
if(x > y)
return;
int mid = x + y >> 1;
int ssf = -1e9, cc = 0;
for(int i = max(mid + m - 1, l2); i <= r2; i++)
{
up(mid, i);
if(t[1].a - a[i].b * 2 + a[mid].b * 2 > ssf)
ssf = t[1].a - a[i].b * 2 + a[mid].b * 2,
cc = i;
}
/// cout<<x<<" "<<y<<" "<<ssf<<" "<<t[1].b<<" "<<l<<" "<<r,down
s4 = max(s4, ssf);
calc(mid + 1, y, cc, r2);
calc(x, mid - 1, l2, cc);
}
void ngha()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> a[i].a >> a[i].b, v.pb(a[i].a);
sort(a + 1, a + 1 + n, cmp);
sort(v.begin(), v.end()) ;
for(i = 1; i <= n; i++)
a[i].a = lower_bound(v.begin(), v.end(), a[i].a) - v.begin() + 1;
build(1,1,n);
l = 1;
r = 0;
s4 = -1e18;
calc(1, n - m + 1, m, n);
cout << s4;
}
