（本篇博客同步于CSDN）

假设有 $x$ 人直接拿钱，我们选择让 $k$ 最小的那 $x$ 个人来拿钱肯定是最优的，因为这样能使得剩下的 $n-x$ 个人选择的余地最大，并且代价最小。把 $k$ 排序后对 $c_{k_{i}}$ 做前缀和。这就转化为了在两个递增数组上依次取一段长为 $x$ 的前缀和一段长为 $m-x$ 的后缀使得和最小，这显然是一个关于 $x$ 的单谷函数，直接无脑三分就能解决。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;

inline int read(){
    int x=0,fh=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') fh=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*fh;
}

const int N=3e5+5;
int k[N],c[N];
ll S1[N],S2[N];

void work(){
    int n=read(),m=read();
    ll ans=1e18;
    fo(i,1,n) k[i]=read();//n个顾客 
    fo(i,1,m) c[i]=read(),S2[i]=S2[i-1]+c[i];//m件礼品
    sort(k+1,k+1+n);
    fo(i,1,n) S1[i]=S1[i-1]+c[k[i]];
    int L=max(0,n-m),R=n,mid1,mid2;
    while(R-L>5){
        mid1=L+(R-L)/3,mid2=R-(R-L)/3;
        ll v1=S1[mid1]+S2[n-mid1],v2=S1[mid2]+S2[n-mid2];
        if(v1<=v2) R=mid2;
        else L=mid1;
    }
    fo(i,L,R) ans=min(ans,S1[i]+S2[n-i]);
    printf("%lld\n",ans);
    //puts("");
}
int main(){
    int T=read();
    while(T--){
        work();
    }
    return 0;
}