该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

Recently, Mr. Liang has become obsessed with a card game and cannot break free from it. The game goes like this: there are n cards arranged in a row from left to right. Each card has a type and a level (initially, all card levels are 1). You can perform the following operations an unlimited number of times: Operation 1: Select a card and play it. Each card type has a value Vi . Playing a level 1 card yields a profit of Vi , playing a level 2 card yields a profit of P · Vi , playing a level 3 card yields a profit of P · P · Vi and so on. However, there is a restriction on the card level, with the maximum level being R. Operation 2: Select two adjacent cards of the same type and level, and merge them into a higher-level card. As his good friend, cv4456 would like to ask you what is the maximum profit Mr. Liang can obtain in the end?

Input

The input consists of multiple test cases. The first line contains a single integer t(1 ≤ t ≤ 50) — the number of test cases. Description of the test cases follows. The first line of each case are four integers,n,m,R,P(1 ≤ n ≤ 100, 1 ≤ m ≤ 20, 1 ≤ R ≤ 20, 1 ≤ P ≤ 10). denoting the number of cards, types of cards, the upper limit of card levels, and the doubling coefficient for higher-level cards. The second line of each case are n integers ai(1 ≤ ai ≤ m),denoting the types of the n cards initially placed on the table.(all cards on the table is level 1) The third line of each case are m integers Vi(1 ≤ Vi ≤ 105 ),denoting the weight of each kinds of card. The data guarantees that there will be no more than 10 groups with a value of n exceeding 20.

Output

For each test case print a single integer —the maximum profit Mr. Liang can obtain in the end.

Samples

1 
7 3 4 3 
1 3 2 3 2 3 3 
1 2 3

32

Limitation

3s, 128mb for each test case.