#pragma GCC optimize(2,3,"Ofast","inline","unroll-loops")
// #pragma GCC target("avx")
#include <bits/stdc++.h>
#define int long long
#define double int
#define MOD1 39989
#define MOD2 1000000000
#define MAXT 40000
using namespace std;
typedef pair<double, int> pdi;

const double eps = 1e-9;

int cmp(double x, double y) {
if(x>y)return -1;
if(x<y)return 1;
  return 0;
}

struct node{
	int x,s,tag;
}a[1000005];

struct line {
  double k, b;
} p[2000005];

int s[2000005];
int cnt;

double calc(int id, int d) { return p[id].b + p[id].k * a[d].x; }

void add(int x0, int y0, int x1, int y1) {
	// cout<<x0<<" "<<y0<<" "<<x1<<" "<<y1<<"\n";
  cnt++;
  if (x0 == x1)  // 特判直线斜率不存在的情况
    p[cnt].k = 0, p[cnt].b = min(y0, y1);
  else
    p[cnt].k = 1 * (y1 - y0) / (x1 - x0), p[cnt].b = y0 - p[cnt].k * x0;
}

void upd(int root, int cl, int cr, int u) {  // 对线段完全覆盖到的区间进行修改
  int &v = s[root], mid = (cl + cr) >> 1;
  int bmid = cmp(calc(u, mid), calc(v, mid));
  if (bmid == 1 || (!bmid && u < v)) swap(u, v);
  int bl = cmp(calc(u, cl), calc(v, cl)), br = cmp(calc(u, cr), calc(v, cr));
  if (bl == 1 || (!bl && u < v)) upd(root << 1, cl, mid, u);
  if (br == 1 || (!br && u < v)) upd(root << 1 | 1, mid + 1, cr, u);
}

void update(int root, int cl, int cr, int l, int r,
            int u) {  // 定位插入线段完全覆盖到的区间
  if (l <= cl && cr <= r) {
    upd(root, cl, cr, u);
    return;
  }
  int mid = (cl + cr) >> 1;
  if (l <= mid) update(root << 1, cl, mid, l, r, u);
  if (mid < r) update(root << 1 | 1, mid + 1, cr, l, r, u);
}

pdi pmax(pdi x, pdi y) {  // pair max函数
  if (cmp(x.first, y.first) == -1)
    return y;
  else if (cmp(x.first, y.first) == 1)
    return x;
  else
    return x.second < y.second ? x : y;
}

pdi query(int root, int l, int r, int d) {  // 查询
  if (r < d || d < l) return {1e18, 0};
  int mid = (l + r) >> 1;
	// cout<<root<<" "<<l<<" "<<r<<" "<<d<<"\n";
  double res = calc(s[root], d);
  if (l == r) return {res, s[root]};
  return pmax({res, s[root]}, pmax(query(root << 1, l, mid, d),
                                   query(root << 1 | 1, mid + 1, r, d)));
}

// int main() {
//   ios::sync_with_stdio(false);
//   int n, lastans = 0;
//   cin >> n;
//   while (n--) {
//     int op;
//     cin >> op;
//     if (op == 1) {
//       int x0, y0, x1, y1;
//       cin >> x0 >> y0 >> x1 >> y1;
//       x0 = (x0 + lastans - 1 + MOD1) % MOD1 + 1,
//       x1 = (x1 + lastans - 1 + MOD1) % MOD1 + 1;
//       y0 = (y0 + lastans - 1 + MOD2) % MOD2 + 1,
//       y1 = (y1 + lastans - 1 + MOD2) % MOD2 + 1;
//       if (x0 > x1) swap(x0, x1), swap(y0, y1);
//       add(x0, y0, x1, y1);
//       update(1, 1, MOD1, x0, x1, cnt);
//     } else {
//       int x;
//       cin >> x;
//       x = (x + lastans - 1 + MOD1) % MOD1 + 1;
//       cout << (lastans = query(1, 1, MOD1, x).second) << endl;
//     }
//   }
//   return 0;
// }

bool cmpp(node A,node B){
	return A.x<B.x;
}
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
int QQ;
int dp[1000005],f[1000005],g[1000005];
int solve(){
	int n,k; n=read(),k=read();
	for(int i=1;i<=n;++i) a[i].x=read();
	for(int i=1;i<=n;++i) a[i].s=read(),a[i].tag=0;
	a[1].tag=1;
	a[n].tag=2;
	sort(a+1,a+n+1,cmpp);
	for(int i=1;i<=n;++i) dp[i]=1e18;
	for(int i=1;i<=n;++i) if(a[i].tag==1) dp[i]=0;
	for(int i=1;i<=4*n;++i) s[i]=0;
	p[0].b=1e18;
	int lim=min(k,13ll);
	if(n<=10000&&QQ)lim=min(k,30ll);
	for(int i=0;i<=lim;++i){
		for(int j=1;j<=n;++j) f[j]=g[j]=1e18;
		for(int j=1;j<=cnt;++j) p[j].k=p[j].b=0;
			for(int j=1;j<=4*n;++j)s[j]=0;
		cnt=0;
		for(int j=1;j<=n;++j){
			f[j]=min(dp[j],(int)query(1,1,n,j).first);
			// cout<<f[j]<<" ";
			add(a[1].x,f[j]-(a[j].x-a[1].x)*a[j].s,a[n].x,f[j]+(a[n].x-a[j].x)*a[j].s);
			update(1,1,n,1,n,cnt);
		}
		for(int j=1;j<=cnt;++j) p[j].k=p[j].b=0;
			for(int j=1;j<=4*n;++j)s[j]=0;
		cnt=0;
		for(int j=n;j>=1;j--){
			g[j]=min(dp[j],(int)query(1,1,n,j).first);
			// cout<<g[j]<<" ";
			add(a[1].x,f[j]+(a[j].x-a[1].x)*a[j].s,a[n].x,f[j]-(a[n].x-a[j].x)*a[j].s);
			update(1,1,n,1,n,cnt);
		}
		for(int j=1;j<=n;++j) dp[j]=min(f[j],g[j]);//cout<<dp[j]<<" ";
		// cout<<"\n";
	}
	for(int i=1;i<=n;++i) if(a[i].tag==2) return dp[i];
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int t; t=read();
	if(t<=50)QQ=1;
	while(t--) write(solve()),putchar('\n');
	return 0;
}