#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
#define int long long
#define lowbit(x) ((x)&(-x))
using namespace std;

inline void down(int &a,const int &b){ if( b!=-1 && (a==-1||a>b) )a=b; }
const int maxn = 310000;
const int maxd = 70;

int n,K;
struct node
{
	int xi,si,id;
}a[maxn];
inline bool cmp(const node &k1,const node &k2){ return k1.xi<k2.xi; }

int fl[maxd][maxn],fr[maxd][maxn];
int t[maxn],tp;
int li[maxn],ri[maxn];

signed main()
{
	/////////////////////////////////////////////////
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int Tcase; cin>>Tcase;
	while(Tcase--)
	{
		cin>>n>>K;
		for(int i=1;i<=n;i++) cin>>a[i].xi;
		for(int i=1;i<=n;i++) cin>>a[i].si;
		for(int i=1;i<=n;i++) a[i].id=i;
		sort(a+1,a+n+1,cmp);
		
		for(int d=0;d<maxd;d++) for(int i=0;i<=n;i++) 
			fl[d][i]=fr[d][i]=-1;
		
		int st,ed;
		for(int i=1;i<=n;i++) 
		{
			if(a[i].id==1) st=i;
			if(a[i].id==n) ed=i;
		}
		
		tp=0;
		for(int i=1;i<=n;i++)
		{
			while(tp && a[t[tp]].si>=a[i].si) tp--;
			li[i]=t[tp];
			t[++tp]=i;
		}
		tp=0;
		for(int i=n;i>=1;i--)
		{
			while(tp && a[t[tp]].si>=a[i].si) tp--;
			ri[i]=t[tp];
			t[++tp]=i;
		}
		
		K=min(K,maxd-1);
		int ans=LLONG_MAX;
		fl[0][st]=fr[0][st]=0;
		for(int d=0;d<=K;d++)
		{
			for(int i=1;i<=n;i++) if(fr[d][i]!=-1)
			{
				if(ed>i)
				{
					down(ans, fr[d][i]+ a[i].si*(a[ed].xi-a[i].xi) );
				}
				int j=ri[i];
				if(j)
				{
					down(fr[d][j], fr[d][i]+ a[i].si*(a[j].xi-a[i].xi) );
					down(fl[d+1][j], fr[d][i]+ a[i].si*(a[j].xi-a[i].xi) );
				}
			}
			for(int i=n;i>=1;i--) if(fl[d][i]!=-1)
			{
				if(ed<i)
				{
					down(ans, fl[d][i]+ a[i].si*(a[i].xi-a[ed].xi) );
				}
				int j=li[i];
				if(j)
				{
					down(fl[d][j], fl[d][i]+ a[i].si*(a[i].xi-a[j].xi) );
					down(fr[d+1][j], fl[d][i]+ a[i].si*(a[i].xi-a[j].xi) );
				}
			}
			down(ans,fr[d][ed]);
			down(ans,fl[d][ed]);
		}
		
		cout<<ans<<'\n';
	}
	
	return 0;
}