Mr. Liang play Card Game

Problem 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 $V_i$. Playing a level 1 card yields a profit of $V_i$, playing a level 2 card yields a profit of $P \cdot V_i$, playing a level 3 card yields a profit of $P \cdot P \cdot 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?

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\le n \le 100,1\le m\le 20,1\le R \le 20,1\le P \le 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\le a_i \le 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\le V_i \le 10^5)$,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.

Sample Input

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

Sample Output

32

Source

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