最近，梁先生沉迷于一款卡牌游戏无法自拔。游戏规则如下：有 $n$ 张卡牌从左到右排成一排。每张卡牌都有一个类型和一个等级（初始时，所有卡牌的等级均为 1）。你可以无限次执行以下操作：

操作 1：选择一张卡牌并打出。每种卡牌类型都有一个价值 $V_i$。打出一张 1 级卡牌可获得 $V_i$ 的收益，打出一张 2 级卡牌可获得 $P \cdot V_i$ 的收益，打出一张 3 级卡牌可获得 $P \cdot P \cdot V_i$ 的收益，以此类推。但是，卡牌等级有限制，最高等级为 $R$。

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

作为他的好朋友，cv4456 想问你，梁先生最终能获得的最大收益是多少？

输入格式

输入包含多个测试用例。第一行包含一个整数 $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 a_i \le m$)，表示初始放置在桌上的 $n$ 张卡牌的类型（桌上所有卡牌初始等级均为 1）。

每个测试用例的第三行包含 $m$ 个整数 $V_i$ ($1 \le V_i \le 10^5$)，表示每种卡牌的价值。

数据保证 $n$ 超过 20 的测试用例组数不超过 10 组。

输出格式

对于每个测试用例，输出一个整数，表示梁先生最终能获得的最大收益。

样例

输入 1

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

输出 1

32