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 V_i , playing a level 2 card yields a profit of P · V_i , playing a level 3 card yields a profit of P · P · V_i 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? 

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 a_i (1 ≤ a_i ≤ 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 V_i (1 ≤ V_i ≤ 10⁵ ),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.

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

2023“钉耙编程”中国大学生算法设计超级联赛（1）