#include <bits/stdc++.h>
using namespace std;
#define int long long int
const int mod = 1e9+7;
struct line
{
int m, c;
};
vector< vector<line> > v;
//Returns true if l2 isnt required anymore
bool bad(line l1, line l2, line l3, int ismin)
{
if(l3.m==l2.m) //Case when l2 and l3 are parallel
{
if(ismin)
return l2.c >= l3.c;
else
return l3.c >= l2.c;
}
if((l1.m - l2.m)*(l1.m - l3.m) > 0) //Checks if both have same signs to reverse the inequality
return (l3.c - l1.c) * (l1.m - l2.m) <= (l2.c - l1.c) * (l1.m - l3.m);
else
return (l3.c - l1.c) * (l1.m - l2.m) >= (l2.c - l1.c) * (l1.m - l3.m);
}
void add(line l, int k, int ismin)
{
while(v[k].size() > 1 && bad(v[k][v[k].size() - 2], v[k][v[k].size() - 1], l, ismin))
v[k].pop_back();
if(v[k].size() == 1 && v[k][0].m == l.m)
{
if(ismin)
{
if(v[k][0].c > l.c)
{
v[k].pop_back();
v[k].push_back(l);
}
}
else
{
if(v[k][0].c < l.c)
{
v[k].pop_back();
v[k].push_back(l);
}
}
}
else if(v[k].empty()||v[k][v[k].size()-1].m!=l.m)
v[k].push_back(l);
}
//Binary search to process query
int query(int x, int k)
{
if(v[k].empty())return -1000000000000000ll;
int l = 0, h = v[k].size();
while(h - l > 1)
{
int mid = (l + h) >> 1;
int intersect = floor(double(v[k][mid].c - v[k][mid - 1].c) / (v[k][mid - 1].m - v[k][mid].m));
if(x <= intersect)
h = mid;
else
l = mid;
}
return v[k][l].m * x + v[k][l].c;
}
#undef int
int main()
{
#define int long long int
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
int n, k;
cin>>n>>k;
vector<int> p(n), q(n);
for(int i = 0;i<n;i++)
cin>>p[i]>>q[i];
v.resize(k+1);
for(int i = 1;i<n;i++)
q[i] = max(q[i-1], q[i]);
for(int i = n-2;i>=0;i--)
p[i] = min(p[i], p[i+1]);
line cur;
cur.m = p[0];
cur.c = 0;
add(cur, 0, 0);
vector<int> ans(k+1);
//Finding the max
for(int i = 1;i<=n;i++)
{
for(int j = 1; j <= min(i, k); j++)
ans[j] = query(q[i-1], j-1);
if(i==n)break;
for(int j = 1;j <= min(i, k); j++)
{
if(ans[j]==-1000000000000000ll)continue;
cur.m = p[i];
cur.c = ans[j];
add(cur, j, 0);
}
}
int ans1 = ans[k];
v.clear();
v.resize(k+1);
cur.m = q[n-1];
cur.c = 0;
add(cur, 0, 1);
//Finding the min
for(int i = n-1;i>=0;i--)
{
for(int j = 1;j<=min(n-i, k); j++)
ans[j] = query(p[i], j-1);
if(i==0)break;
for(int j = 1;j<=min(n-i, k);j++)
{
if(ans[j]==-1000000000000000ll)continue;
cur.m = q[i-1];
cur.c = ans[j];
add(cur, j, 1);
}
}
cout<<ans[k]<<" "<<ans1<<endl;
v.clear();
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGludCBsb25nIGxvbmcgaW50CmNvbnN0IGludCBtb2QgPSAxZTkrNzsKCnN0cnVjdCBsaW5lCnsKICAgIGludCBtLCBjOwp9Owp2ZWN0b3I8IHZlY3RvcjxsaW5lPiA+IHY7Ci8vUmV0dXJucyB0cnVlIGlmIGwyIGlzbnQgcmVxdWlyZWQgYW55bW9yZQpib29sIGJhZChsaW5lIGwxLCBsaW5lIGwyLCBsaW5lIGwzLCBpbnQgaXNtaW4pCnsKICAgIGlmKGwzLm09PWwyLm0pIC8vQ2FzZSB3aGVuIGwyIGFuZCBsMyBhcmUgcGFyYWxsZWwKICAgIHsKICAgICAgICBpZihpc21pbikKICAgICAgICAgICAgcmV0dXJuIGwyLmMgPj0gbDMuYzsKICAgICAgICBlbHNlCiAgICAgICAgICAgIHJldHVybiBsMy5jID49IGwyLmM7CiAgICB9CiAgICBpZigobDEubSAtIGwyLm0pKihsMS5tIC0gbDMubSkgPiAwKSAvL0NoZWNrcyBpZiBib3RoIGhhdmUgc2FtZSBzaWducyB0byByZXZlcnNlIHRoZSBpbmVxdWFsaXR5CiAgICAgICAgcmV0dXJuIChsMy5jIC0gbDEuYykgKiAobDEubSAtIGwyLm0pIDw9IChsMi5jIC0gbDEuYykgKiAobDEubSAtIGwzLm0pOwogICAgZWxzZQogICAgICAgIHJldHVybiAobDMuYyAtIGwxLmMpICogKGwxLm0gLSBsMi5tKSA+PSAobDIuYyAtIGwxLmMpICogKGwxLm0gLSBsMy5tKTsKfQp2b2lkIGFkZChsaW5lIGwsIGludCBrLCBpbnQgaXNtaW4pCnsKICAgIHdoaWxlKHZba10uc2l6ZSgpID4gMSAmJiBiYWQodltrXVt2W2tdLnNpemUoKSAtIDJdLCB2W2tdW3Zba10uc2l6ZSgpIC0gMV0sIGwsIGlzbWluKSkKICAgICAgICB2W2tdLnBvcF9iYWNrKCk7CiAgICBpZih2W2tdLnNpemUoKSA9PSAxICYmIHZba11bMF0ubSA9PSBsLm0pCiAgICB7CiAgICAgICAgaWYoaXNtaW4pCiAgICAgICAgewogICAgICAgICAgICBpZih2W2tdWzBdLmMgPiBsLmMpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHZba10ucG9wX2JhY2soKTsKICAgICAgICAgICAgICAgIHZba10ucHVzaF9iYWNrKGwpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIGlmKHZba11bMF0uYyA8IGwuYykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgdltrXS5wb3BfYmFjaygpOwogICAgICAgICAgICAgICAgdltrXS5wdXNoX2JhY2sobCk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBlbHNlIGlmKHZba10uZW1wdHkoKXx8dltrXVt2W2tdLnNpemUoKS0xXS5tIT1sLm0pCiAgICAgICAgdltrXS5wdXNoX2JhY2sobCk7Cn0KLy9CaW5hcnkgc2VhcmNoIHRvIHByb2Nlc3MgcXVlcnkKaW50IHF1ZXJ5KGludCB4LCBpbnQgaykKewogICAgaWYodltrXS5lbXB0eSgpKXJldHVybiAtMTAwMDAwMDAwMDAwMDAwMGxsOwogICAgaW50IGwgPSAwLCBoID0gdltrXS5zaXplKCk7CiAgICB3aGlsZShoIC0gbCA+IDEpCiAgICB7CiAgICAgICAgaW50IG1pZCA9IChsICsgaCkgPj4gMTsKICAgICAgICBpbnQgaW50ZXJzZWN0ID0gZmxvb3IoZG91YmxlKHZba11bbWlkXS5jIC0gdltrXVttaWQgLSAxXS5jKSAvICh2W2tdW21pZCAtIDFdLm0gLSB2W2tdW21pZF0ubSkpOwogICAgICAgIGlmKHggPD0gaW50ZXJzZWN0KQogICAgICAgICAgICBoID0gbWlkOyAKICAgICAgICBlbHNlCiAgICAgICAgICAgIGwgPSBtaWQ7CiAgICB9CiAgICByZXR1cm4gdltrXVtsXS5tICogeCArIHZba11bbF0uYzsKfQoKI3VuZGVmIGludAppbnQgbWFpbigpCnsgICAKI2RlZmluZSBpbnQgbG9uZyBsb25nIGludAogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsKICAgIGNpbi50aWUoMCk7CiAgICBjb3V0LnRpZSgwKTsKICAgIAogICAgaW50IHQ7CiAgICBjaW4+PnQ7CiAgICB3aGlsZSh0LS0pCiAgICB7CiAgICAgICAgaW50IG4sIGs7CiAgICAgICAgY2luPj5uPj5rOwogICAgICAgIHZlY3RvcjxpbnQ+IHAobiksIHEobik7CiAgICAgICAgZm9yKGludCBpID0gMDtpPG47aSsrKQogICAgICAgICAgICBjaW4+PnBbaV0+PnFbaV07CiAgICAgICAgdi5yZXNpemUoaysxKTsKICAgICAgICBmb3IoaW50IGkgPSAxO2k8bjtpKyspCiAgICAgICAgICAgIHFbaV0gPSBtYXgocVtpLTFdLCBxW2ldKTsKICAgICAgICBmb3IoaW50IGkgPSBuLTI7aT49MDtpLS0pCiAgICAgICAgICAgIHBbaV0gPSBtaW4ocFtpXSwgcFtpKzFdKTsKICAgICAgICBsaW5lIGN1cjsKICAgICAgICBjdXIubSA9IHBbMF07CiAgICAgICAgY3VyLmMgPSAwOwogICAgICAgIGFkZChjdXIsIDAsIDApOwogICAgICAgIHZlY3RvcjxpbnQ+IGFucyhrKzEpOwogICAgICAgIC8vRmluZGluZyB0aGUgbWF4CiAgICAgICAgZm9yKGludCBpID0gMTtpPD1uO2krKykKICAgICAgICB7CiAgICAgICAgICAgIGZvcihpbnQgaiA9IDE7IGogPD0gbWluKGksIGspOyBqKyspCiAgICAgICAgICAgICAgICBhbnNbal0gPSBxdWVyeShxW2ktMV0sIGotMSk7CiAgICAgICAgICAgIGlmKGk9PW4pYnJlYWs7CiAgICAgICAgICAgIGZvcihpbnQgaiA9IDE7aiA8PSBtaW4oaSwgayk7IGorKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYoYW5zW2pdPT0tMTAwMDAwMDAwMDAwMDAwMGxsKWNvbnRpbnVlOwogICAgICAgICAgICAgICAgY3VyLm0gPSBwW2ldOwogICAgICAgICAgICAgICAgY3VyLmMgPSBhbnNbal07CiAgICAgICAgICAgICAgICBhZGQoY3VyLCBqLCAwKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBpbnQgYW5zMSA9IGFuc1trXTsKICAgICAgICB2LmNsZWFyKCk7CiAgICAgICAgdi5yZXNpemUoaysxKTsKICAgICAgICBjdXIubSA9IHFbbi0xXTsKICAgICAgICBjdXIuYyA9IDA7CiAgICAgICAgYWRkKGN1ciwgMCwgMSk7CiAgICAgICAgLy9GaW5kaW5nIHRoZSBtaW4KICAgICAgICBmb3IoaW50IGkgPSBuLTE7aT49MDtpLS0pCiAgICAgICAgewogICAgICAgICAgICBmb3IoaW50IGogPSAxO2o8PW1pbihuLWksIGspOyBqKyspCiAgICAgICAgICAgICAgICBhbnNbal0gPSBxdWVyeShwW2ldLCBqLTEpOwogICAgICAgICAgICBpZihpPT0wKWJyZWFrOwogICAgICAgICAgICBmb3IoaW50IGogPSAxO2o8PW1pbihuLWksIGspO2orKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYoYW5zW2pdPT0tMTAwMDAwMDAwMDAwMDAwMGxsKWNvbnRpbnVlOwogICAgICAgICAgICAgICAgY3VyLm0gPSBxW2ktMV07CiAgICAgICAgICAgICAgICBjdXIuYyA9IGFuc1tqXTsKICAgICAgICAgICAgICAgIGFkZChjdXIsIGosIDEpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGNvdXQ8PGFuc1trXTw8IiAiPDxhbnMxPDxlbmRsOwogICAgICAgIHYuY2xlYXIoKTsKICAgIH0KCiAgICByZXR1cm4gMDsKfQ==