最近，梁老师沉迷于纸牌游戏，无法自拔。 游戏是这样的：有$n$张牌从左到右排成一排。 每张卡牌都有一个类型和一个等级（最初，所有卡牌等级均为 1）。 您可以无限次执行以下操作：

操作1：选择一张牌并打出。 每种卡类型都有一个值 $V_i$。 玩 1 级卡产生的利润为 $V_i$，玩 2 级卡产生的利润为 $P \cdot V_i$，玩 3 级卡产生的利润为 $P \cdot P \cdot V_i$ 等等 。 不过卡牌等级有限制，最高等级为$R$。

操作2：选择相邻的两张相同类型和等级的卡牌，将其合并为一张更高等级的卡牌。

作为他的好朋友，cv4456想请问您梁先生到底能获得的最大利润是多少？

Input

输入由多个测试用例组成。 第一行包含一个整数 $t$($1 \le t \le 50$) — 测试用例的数量。 测试用例的描述如下。

每种测试用例的第一行是四个整数 $n$,$m$,$R$,$P$($1 \le n \le 100$, $1 \le m \le 20$, $1 \le R \le 20$, $1 \le P \le 10$)。 表示卡牌数量、卡牌类型、卡牌等级上限以及卡牌的倍增系数。

每个测试用例的第二行是$n$个整数$a_i$($1 \le ai \le m$)，表示最初放在桌上的$n$张牌的类型。（桌上的牌都是1级）

每种测试用例的第三行是$m$个整数$V_i$（$1 \le V_i \le 10^5$），表示每种卡片的利润。

数据保证$n$的值超过20的组不会超过10个。

Output

对于每个测试用例打印一个整数——梁老师最终可以获得的最大利润。

Example

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

32

Example explain

梁老师可以先将第 1,3,5 张牌打出，得到 $1+2+2=5$ 点利润，手牌变为 $(3^1,3^1,3^1,3^1)$。然后将第 1,2 张牌合并，第 3,4 张牌合并，手牌变为 $(3^2,3^2)$。最后将第 1,2 张牌合并然后打出，这样他就可以获得 $3*3^{3-1}=27$ 点利润，总共获得 $5+27=32$ 点利润。

Limitation

时间限制：3秒

内存限制：128 MB