#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
ll X[301000],G[300100];
#define pi pair<ll,ll>
#define mp make_pair
const int I=1e9;
#define pb push_back
#define F first
#define S second
ll d1[101000],d2[100100],o1[100100],o2[101000];
ll d1_[101000],d2_[101000];
int s1,s2;
pi sta[101000];int top;
pi operator - (const pi &a,const pi &b){return mp(a.F-b.F,a.S-b.S);}
__int128 cro(pi a,pi b){return ((__int128)a.F)*b.S-((__int128)b.F)*a.S;}
ll E(pi a,ll x){return a.F*x+a.S;} 
void sol(){
	scanf("%d%d",&n,&m);m=min(m,100);
	vector<pi>v1,v2;
	for(int i=1;i<=n;i++)scanf("%lld",&X[i]);
	for(int i=1;i<=n;i++)scanf("%lld",&G[i]);
	if(X[1]>X[n]){for(int i=1;i<=n;i++)X[i]=I+1-X[i];}
	for(int i=2;i<n;i++){
		if(X[i]>X[n])continue;
		if(X[i]<X[1])v1.pb(mp(X[1]-X[i],G[i]));
		else v2.pb(mp(X[i]-X[1],G[i]));
	}
	sort(v1.begin(),v1.end()),sort(v2.begin(),v2.end());
	vector<pi>fz;
	ll ns=G[1];
	for(pi e:v1)if(ns>e.S)ns=e.S,fz.pb(e);v1=fz;
	fz.clear();
	ns=G[1];
	for(pi e:v2)if(ns>e.S)ns=e.S,fz.pb(e);v2=fz;
	ll ans=(X[n]-X[1])*G[1];
	s1=v1.size(),s2=v2.size();
	d1[0]=d2[0]=0;
	for(int i=1;i<=s1;i++)o1[i]=((i>1)?v1[i-2].S:G[1])*(v1[i-1].F-((i>1)?v1[i-2].F:0)),d1[i]=d1[i-1]+o1[i];
	for(int i=1;i<=s2;i++)o2[i]=((i>1)?v2[i-2].S:G[1])*(v2[i-1].F-((i>1)?v2[i-2].F:0)),d2[i]=d2[i-1]+o2[i];
	if(s2)ans=min(ans,d2[s2]+v2[s2-1].S*(X[n]-X[1]-v2[s2-1].F));
	for(int e=1;e<=m;e++){
		if(e&1){for(int i=1;i<=s1;i++)ans=min(ans,d1[i]+(X[n]-X[1]+v1[i-1].F)*v1[i-1].S);}
		else{for(int i=1;i<=s2;i++)ans=min(ans,d2[i]+(X[n]-X[1]-v2[i-1].F)*v2[i-1].S);}
		for(int i=1;i<=s1;i++)d1_[i]=I;for(int i=1;i<=s2;i++)d2_[i]=I;
		//d1_i+S[i](X[i]+X[j])->d2[j]
		top=0;
		for(int i=s1;i;i--){
			pi ut=mp(v1[i-1].S,d1[i]+v1[i-1].S*v1[i-1].F);
			while(top&&cro(sta[top]-sta[top-1],ut-sta[top])<=0)top--;
			sta[++top]=ut;
		}
		for(int i=s2,j=1;i;i--){
			ll A=v2[i-1].S;
			while(j<top&&E(sta[j],A)>E(sta[j+1],A))j++;
			d2_[i]=min(d2_[i],E(sta[j],A));
		}
		top=0;
		for(int i=s2;i;i--){
			pi ut=mp(v2[i-1].S,d2[i]+v2[i-1].S*v2[i-1].F);
			while(top&&cro(sta[top]-sta[top-1],ut-sta[top])<=0)top--;
			sta[++top]=ut;
		}
		for(int i=s1,j=1;i;i--){
			ll A=v1[i-1].S;
			while(j<top&&E(sta[j],A)>E(sta[j+1],A))j++;
			d1_[i]=min(d1_[i],E(sta[j],A));
		}
		for(int i=2;i<=s1;i++)d1_[i]=min(d1_[i],d1_[i-1]+o1[i]);
		for(int i=2;i<=s2;i++)d2_[i]=min(d2_[i],d2_[i-1]+o2[i]);
		for(int i=1;i<=s1;i++)d1[i]=d1_[i];
		for(int i=1;i<=s2;i++)d2[i]=d2_[i];
	}
	printf("%lld\n",ans);
}
int main(){
	int T;scanf("%d",&T);
	while(T--)sol();
	return 0;
}