← 返回题目列表

Codeforces · 1621/F

F. 奇怪的指令

中文机器翻译题面 查看原题

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。