Description

有n块石头排成一行，从左到右依次编号为1到n，相邻两块石头之间的距离为1。有m只青蛙，开始时都位于1号石头
，它们都需要跳到n号石头上。青蛙只能跳到更靠右的石头上。如果第i只青蛙的某次跳跃的距离超过d，那么需要
付出ci的代价。求出满足以下两个条件时，总代价的最小值：
(1) 石头a1,a2,a3,…,ak必须被跳到恰好一次。
(2) 其它石头(不包含1号石头和n号石头)不能被跳到。
有多组数据。

Input

第一行一个整数t表示数据组数。
每组数据第一行四个整数n,m,k,d，第二行m个整数c1~cm，第三行k个整数a1~ak。
t<=10，3<=n<=10^9，1<=d<=10^9，1<=m,k<=10^5，
1<ai<n，ai互不相同。

Output

每组数据输出一行一个整数表示答案。

Sample Input

2
10 2 3 3
4 7
4 8 7
10 2 2 3
4 7
9 5

Sample Output

4
15

题解

经过观察可以发现，因为所有青蛙的极限距离D是相同的，所以青蛙之间的费用是可以互换的。
同时，我们可以发现，一旦一只青蛙需要付费跳跃一次，我们倒不如让它直接付费从1号石子直接跳跃到n号石子，因为将中间的石子留给其他青蛙，是有概率减少他们付费跳跃的次数的。
所以，我们二分最多可以有多少只青蛙可以同时免费从1号石子跳到n号石子，那么其他青蛙就直接从1号石子付费跳跃到n号石子，免费的那部分明显贪心取费用的最大值。
如果所有青蛙都需要付费跳跃才能完成任务，那么就选取费用最低的青蛙付费跳跃完所有石子，然后其他青蛙直接从1号到n号。

代码

#include <cstdio>
#include <queue>
#include <algorithm>
#define LL long long
using namespace std;

const int MAXN=1e5+50;

queue<int> que;
int c[MAXN], s[MAXN];
int n, m, D, K; 

inline int calc(int p){
    int ret=0;
    while(!que.empty()) que.pop();
    for (int i=1; i<=p; i++) que.push(1);
    for (int i=1; i<=K; i++){
        int now=que.front(); que.pop();
        if (s[i]-now>D) ++ret;
        que.push(s[i]);
    }
    for (int i=1; i<=p; i++){
        int now=que.front(); que.pop();
        if (n-now>D) ++ret;
    }
    return ret;
}

inline void solve(int T){
    scanf("%d%d%d%d", &n, &m, &K, &D);
    for (int i=1; i<=m; i++) scanf("%d", &c[i]);
    for (int i=1; i<=K; i++) scanf("%d", &s[i]);

    sort(c+1, c+m+1);
    sort(s+1, s+K+1);

    int left=1, right=m, mx=0;
    while(left<=right){
        int mid=(left+right)/2;
        if (calc(mid)==0){
            mx=max(mx, mid);
            left=mid+1;
        }else right=mid-1;
    }

    LL ans=0;
    if (mx==0) {
        ans=1LL*calc(1)*c[1]; 
        for (int i=2; i<=m; i++) ans+=c[i];
    }else{
        for (int i=max(0, m-mx); i>=1; i--) ans=ans+c[i];
    }

    printf("%lld\n", ans);
}

int main(){
    // freopen("in.txt", "r", stdin);
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}