#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(int)a;i<(int)b;i++)
#define all(p) p.begin(),p.end()
using ll =long long;

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<>>{
    static const ll inf = LLONG_MAX;
    ll div(ll a,ll b){
        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){
        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;
    }
};
void solve(){
    int N,K;
    cin>>N>>K;
    K=min(K,40);
    vector<ll> X(N),S(N);
    rep(i,0,N) cin>>X[i];
    rep(i,0,N) cin>>S[i];
    ll ans=(1ll<<60);
    rep(rp,0,2){
        rep(i,0,N) X[i]*=-1;
        vector<int> order(N);
        rep(i,0,N) order[i]=i;
        sort(all(order),[&](int l,int r){
            return X[l]<X[r];
        });
        vector<ll> dp(N,1ll<<60);
        dp[0]=0;
        ll sign=1;
        rep(rvrv,0,K+1){
            LineContainer L;
            sign *= -1;
            reverse(all(order));
            rep(i,0,N){
                int a=order[i];
                if(i){
                    dp[a]=min(dp[a],-L.query(X[a]*sign));
                }
                ll k=S[a];
                ll m=dp[a]-X[a]*S[a]*sign;
                L.add(-k,-m);
            }
        }
        ans=min(ans,dp[N-1]);
    }
    cout<<ans<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        solve();
    }
}
/*
2
4 2
3 2 1 6
3 1 1 3
2 0
1 2
1 2
*/