Dasha 有 $$$10^{100}$$$ 硬币。最近,她发现了一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$ 以及一些允许更改该字符串的操作(她可以对每个操作执行任意次数):
1. 将$$$s$$$的子串00替换为0,获得$$$a$$$币。
2. 将 $$$s$$$ 的子串 11 替换为 1,并获得 $$$b$$$ 硬币。
3.从$$$s$$$中的任意位置删除0并支付$$$c$$$硬币。
事实证明,Dasha在执行此操作时应遵循以下规则:
- 禁止连续执行两次具有相同奇偶校验的操作。操作按上面给出的顺序用整数 $$$1$$$-$$$3$$$ 进行编号。
请计算一下,按照这个规则,做这些操作,大傻能获得的最大利润是多少。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含四个整数 $$$n$$$、$$$a$$$、$$$b$$$、$$$c$$$ ($$$1 \leq n \leq 10^5, 1 \leq a, b, c \leq 10^9$$$)。
每个测试用例的第二行包含一个长度为$$$n$$$的二进制字符串$$$s$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例打印答案。
示例
输入 #1
3 5 2 2 1 01101 6 4 3 5 110001 6 3 2 1 011110
输出 #1
3 11 4
注意
在第一个测试用例中,最佳操作序列之一是 01101 $$$\rightarrow$$$ 0101 $$$\rightarrow$$$ 011 $$$\rightarrow$$$ 01。此操作序列按顺序由操作 $$$2$$$、$$$3$$$ 和 $$$2$$$ 组成。它满足所有规则并带来利润$$$3$$$。可以看出,在这个测试用例中不可能获得更高的利润,所以答案是$$$3$$$。
在第二个测试用例中,最佳操作序列之一是 110001 $$$\rightarrow$$$ 11001 $$$\rightarrow$$$ 1001 $$$\rightarrow$$$ 101。
在第三个测试用例中,最佳操作顺序之一是 011110 $$$\rightarrow$$$ 01110 $$$\rightarrow$$$ 1110 $$$\rightarrow$$$ 110 $$$\rightarrow$$$ 11 $$$\rightarrow$$$ 1。