Description

有n块石头排成一行，从左到右依次编号为1到n，相邻两块石头之间的距离为1。有m只青蛙，开始时都位于1号石头 ，它们都需要跳到n号石头上。

青蛙只能跳到更靠右的石头上。如果第i只青蛙的某次跳跃的距离超过d，那么需要付出ci的代价。求出满足以下两个条件时，总代价的最小值：

(1) 石头a1,a2,a3,…,ak必须被跳到恰好一次。

(2) 其它石头(不包含1号石头和n号石头)不能被跳到。

有多组数据。

Format

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

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

Samples

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

4
15