#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
using namespace std;
using pii = pair<int,int>;
using ll = long long;
using pll = pair<ll,ll>;
using vi = vector<int>;
 
using ld = long double;

mt19937_64 rnd(1);
 
#define all(x) (x).begin(), (x).end()
 
const int maxn = 3e5+10, inf = 1e9+100;
const ll linf = 1e18+100;
const int mod = 998244353;
 
const ld eps = 1e-9;
const ld PI = acos(-1.L);

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
    k = -k, m = -m;
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return -l.k * x - l.m;
	}
};

ll x[maxn], s[maxn];
ll dp[31][maxn];
void solvee(){
  int n,k;
  cin >> n >> k;
  k = min(k, 30);
  for(int i=0;i<n;i++)cin >> x[i];
  for(int i=0;i<n;i++)cin >> s[i];
  int stx = x[0], tarx = x[n-1];
  map<ll,ll> sss;
  for(int i=0;i<n;i++){
    if(!sss.count(x[i]))sss[x[i]]=s[i];
    else sss[x[i]] = min(sss[x[i]], s[i]);
  }
  n = sss.size();
  {
    int i = 0;
  for(auto [xv,sv] : sss) {
    x[i] = xv, s[i] = sv;
    i++;
  }
  }
  int st, tar;
  for(int i=0;i<n;i++){
    if(x[i]==stx)st = i;
    if(x[i]==tarx)tar = i;
  }
  // cerr << st << " " << tar << endl;
  for(int j=0;j<=k;j++)for(int i=0;i<n;i++)dp[j][i] = linf;
  dp[0][st] = 0;
  for(int ind=0;ind<=k;ind++){
    dp[ind][st] = 0;
    // advance same side
    LineContainer cvx;
    // right
    cvx.add(s[st],dp[ind][st]-x[st]*s[st]);
    for(int i=st+1;i<n;i++){
      dp[ind][i] = min(dp[ind][i], cvx.query(x[i]));
      cvx.add(s[i],dp[ind][i]-x[i]*s[i]);
    }
    // left
    cvx.clear();
    cvx.add(-s[st],dp[ind][st]+x[st]*s[st]);
    for(int i=st-1;i>=0;i--){
      dp[ind][i] = min(dp[ind][i], cvx.query(x[i]));
      cvx.add(-s[i],dp[ind][i]+x[i]*s[i]);
    }
    if(ind==k)break;
    // switch to other side
    // right -> left
    cvx.clear();
    for(int i=st+1;i<n;i++){
      cvx.add(-s[i],dp[ind][i]+x[i]*s[i]);
    }
    for(int i=st-1;i>=0;i--){
      dp[ind+1][i] = min(dp[ind+1][i],cvx.query(x[i]));
    }
    // left -> right
    cvx.clear();
    for(int i=st-1;i>=0;i--){
      cvx.add(s[i],dp[ind][i]-x[i]*s[i]);
      // cerr << "LR LINE " << s[i] << " " << dp[ind][i]-x[i]*s[i] << endl;
      // cerr << cvx.query(6);
    }
    for(int i=st+1;i<n;i++){
      dp[ind+1][i] = min(dp[ind+1][i],cvx.query(x[i]));
    }
  }
  // for(int i=0;i<=k;i++){
    // for(int j=0;j<n;j++)cerr << dp[i][j] << " \n"[j==n-1];
  // }
  ll ans = linf;
  for(int i=0;i<=k;i++)ans=min(ans, dp[i][tar]);
  cout << ans << "\n";
}

void solve(){
  int tc;
  cin >> tc;
  while(tc--){
    solvee();
  }
}
 
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout<<fixed;
  cout.precision(20);
  cerr << fixed;
  cerr.precision(5);
  solve();
}