F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5438. -- 青蛙

5438: 青蛙

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 38  Solved: 18
[Submit][Status][Discuss]

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

HINT

Source

[Submit][Status][Discuss]

HOME Back