Strange Instructions

题意翻译

Dasha 拥有 $10^{100}$ 枚硬币。最近，她发现了一个长度为 $n$ 的 $0/1$ 串。每次她可以执行如下三种操作中的一种，但是需要保证任意连续的两次操作的编号奇偶性不同： 1. 将 $s$ 的**恰好一个**子串 `00` 替换成 `0`，获得 $a$ 枚硬币。 2. 将 $s$ 的**恰好一个**子串 `11` 替换成 `1`，获得 $b$ 枚硬币。 3. 将 $s$ 的**恰好一个**子串 `0` 移除，**花费** $c$ 枚硬币。 Dasha 想知道她能够通过上述操作得到的硬币最多有多少枚。你能帮帮她吗？ 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 10^4$。 - $1\leqslant n\leqslant 10^5$，$1\leqslant a,b,c\leqslant 10^9$，$\sum n\leqslant 2\times 10^5$。 Translated by Eason_AC 2022.1.4

题目描述

Dasha has $ 10^{100} $ coins. Recently, she found a binary string $ s $ of length $ n $ and some operations that allows to change this string (she can do each operation any number of times): 1. Replace substring 00 of $ s $ by 0 and receive $ a $ coins. 2. Replace substring 11 of $ s $ by 1 and receive $ b $ coins. 3. Remove 0 from any position in $ s $ and pay $ c $ coins. It turned out that while doing this operations Dasha should follow the rule: - It is forbidden to do two operations with the same parity in a row. Operations are numbered by integers $ 1 $ - $ 3 $ in the order they are given above. Please, calculate what is the maximum profit Dasha can get by doing these operations and following this rule.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The first line of each test case contains four integers $ n $ , $ a $ , $ b $ , $ c $ ( $ 1 \leq n \leq 10^5, 1 \leq a, b, c \leq 10^9 $ ). The second line of each test case contains a binary string $ s $ of length $ n $ . It is guaranteed that the total sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case print the answer.

输入输出样例

输入样例 #1

3
5 2 2 1
01101
6 4 3 5
110001
6 3 2 1
011110

输出样例 #1

3
11
4

说明

In the first test case one of the optimal sequences of operations is 01101 $ \rightarrow $ 0101 $ \rightarrow $ 011 $ \rightarrow $ 01. This sequence of operations consists of operations $ 2 $ , $ 3 $ and $ 2 $ in this order. It satisfies all rules and gives profit $ 3 $ . It can be shown that it is impossible to achieve higher profit in this test case, so the answer is $ 3 $ . In the second test case one of the optimal sequences of operations is 110001 $ \rightarrow $ 11001 $ \rightarrow $ 1001 $ \rightarrow $ 101. In the third test case one of the optimal sequences of operations is 011110 $ \rightarrow $ 01110 $ \rightarrow $ 1110 $ \rightarrow $ 110 $ \rightarrow $ 11 $ \rightarrow $ 1.