给定四个整数 $$$n$$$、$$$c_0$$$、$$$c_1$$$ 和 $$$h$$$ 以及长度为 $$$n$$$ 的二进制字符串 $$$s$$$。
二进制字符串是由字符 $$$0$$$ 和 $$$1$$$ 组成的字符串。
您可以更改字符串 $$$s$$$ 的任何字符(更改后该字符串应该仍然是二进制)。您应该为每次更改支付 $$$h$$$ 硬币。
经过一些更改(可能为零)后,您想要购买该字符串。要购买字符串,您应该购买其所有字符。要购买角色$$$0$$$,您应该支付$$$c_0$$$硬币,要购买角色$$$1$$$,您应该支付$$$c_1$$$硬币。
找出购买该字符串所需的最少硬币数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10$$$) — 测试用例的数量。接下来的 $$$2t$$$ 行包含测试用例的描述。
每个测试用例描述的第一行包含四个整数 $$$n$$$, $$$c_{0}$$$, $$$c_{1}$$$, $$$h$$$ ($$$1 \leq n, c_{0}, c_{1}, h \leq 1000$$$)。
每个测试用例描述的第二行包含长度为$$$n$$$的二进制字符串$$$s$$$。
输出
对于每个测试用例,打印一个整数 - 购买该字符串所需的最小硬币数量。
示例
输入 #1
6 3 1 1 1 100 5 10 100 1 01010 5 10 1 1 11111 5 1 10 1 11111 12 2 1 10 101110110101 2 100 1 10 00
输出 #1
3 52 5 10 16 22
注意
在第一个测试用例中,您可以购买所有角色并支付 $$$3$$$ 硬币,因为 $$$0$$$ 和 $$$1$$$ 两个角色都花费 $$$1$$$ 硬币。
在第二个测试用例中,您可以首先将字符串的第$$$2$$$个和第$$$4$$$个符号从$$$1$$$更改为$$$0$$$,并为此支付$$$2$$$硬币。您的字符串将为 $$$00000$$$。之后,您可以购买该字符串并支付 $$$5 \cdot 10 = 50$$$ 硬币。支付的硬币总数为$$$2 + 50 = 52$$$。