BZPRO
#5438. 青蛙
内存限制：256 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
有n块石头排成一行，从左到右依次编号为1到n，相邻两块石头之间的距离为1。有m只青蛙，开始时都位于1号石头
，它们都需要跳到n号石头上。青蛙只能跳到更靠右的石头上。如果第i只青蛙的某次跳跃的距离超过d，那么需要
付出ci的代价。求出满足以下两个条件时，总代价的最小值：
(1)
石头a1,a2,a3,…,ak必须被跳到恰好一次。
(2)
其它石头(不包含1号石头和n号石头)不能被跳到。
有多组数据。
输入格式
第一行一个整数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互不相同。
输出格式
每组数据输出一行一个整数表示答案。
样例
样例输入
2
10 2 3 3
4 7
4 8 7
10 2 2 3
4 7
9 5
样例输出
4
15
数据范围与提示
BZPRO