题目
最近，梁迷上了一种纸牌游戏，无法摆脱它。游戏是这样的：从左到右排列着n张牌。每张卡片都有一种类型和一个等级（最初，所有卡片等级都是1）。您可以无限次执行以下操作：


操作1：选择一张牌并玩。每种牌类型都有一个值ViV_iVi​. 打一张一级牌获利Vi，打一张二级牌获利P·Vi​, 打一张三级牌可以获得P·P·Vi的利润​ 等等。然而，卡级别有限制，最大级别为R。


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


作为他的好朋友，cv4456想问你，梁先生最终能获得的最大利润是多少？
输入
输入由多个测试用例组成。第一行包含单个整数t（1≤t≤50）——测试用例的数量。测试用例的描述如下。


每种情况的第一行是四个整数，n、m、R、P，表示牌的数量、牌的类型、牌级别的上限以及更高级别牌的倍增系数。


每种情况的第二行是n个整数ai（1≤ai≤m），表示最初放在表上的n张卡片的类型。（桌上的所有牌都是1级）


每种情况的第三行是m整数Vi（1≤Vi≤105），表示每种卡片的重量。


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