Strange Instructions
Contest: Hello 2022
Difficulty rating: 2700
Tags: data structures, greedy, implementation

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.

Input format:
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$$$.

Output format:
For each test case print the answer.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3
5 2 2 1
01101
6 4 3 5
110001
6 3 2 1
011110

Example output:
3
11
4

Editorial:
From the rule $$$4$$$ it follows that the sequence of types of operations looks like $$$\ldots$$$, ($$$1$$$ or $$$3$$$), $$$2$$$, ($$$1$$$ or $$$3$$$), $$$2$$$, ($$$1$$$ or $$$3$$$), $$$\ldots$$$.
One can suppose that operation $$$1$$$ is "better" than operation $$$3$$$ so we can (in optimal solution) do all operations of type $$$3$$$ after all operations of type $$$1$$$. However it is now always the truth: for example for $$$s = 00101$$$ with large $$$a$$$ and $$$b$$$ and small $$$c$$$ it is optimal to do operations of types $$$3$$$, $$$2$$$ and $$$1$$$ in this order to get profit of $$$a+b-c$$$ ($$$00101 \rightarrow 0011 \rightarrow 011 \rightarrow 01$$$). But it turns out that it is the only case when we should do operation of type $$$1$$$ after the operation of the type $$$3$$$: we can do no more than one such operation $$$1$$$ and we can do it in the end. I will prove it later.
Now we know how does the operation sequence look like. Let's now think what zeroes and ones we will remove on each step. Obviously, the only case we should use operation of type $$$3$$$ is to remove the last $$$0$$$ in the block (block of zeroes or ones is the unextendable substring constisting only of zeroes or ones) otherwise we can use the operation of type $$$1$$$.
Let's now think that string is a sequence of blocks. Obiviously, all zeroes/ones in one block are indistinguishable. Let's look how does the number of possible operations of type $$$2$$$ changes after each operation. It is the number of ones minus the number of blocks of ones. After the operation of type $$$1$$$ the blocks structure doesn't changes; after the operation of type $$$2$$$ the blocks structure also doesn't change but the number of ones reduces by one; after the operation of type of $$$3$$$ the number of ones doesn't change, but two blocks of ones are merged together (if we removed not the first or last block).
So, the number of possible operations of type $$$2$$$ decreaces by one after the operation of type $$$2$$$ and can increase by one after the operation of type $$$3$$$. Also we can see that the operation of type $$$2$$$ can't affect any block of zeroes in any way. From here it follows that all operations of type $$$2$$$ are indistinguishable and we should only care about the amount of possible such operations.
Also it follows that using operation $$$3$$$ to remove one of the middle blocks is always better than using operation $$$3$$$ to remove the block from the side.
Also it follows that if we have no possible operation of type $$$2$$$ remaining the only way to not stop doing operations it to do operation of type $$$3$$$ with one of the middle blocks. However, after it we will do operation of type $$$2$$$ and will come back to this situation again. Here, in cases $$$b < c$$$ or no operation of type $$$3$$$ available we can do operation of type $$$1$$$ (if it is possible) and stop.
I claim that the case above is the only case when we should do the operation of type $$$1$$$ after the operation $$$3$$$. Assume it is not. Then we have consecutive operations of types $$$3$$$, $$$2$$$, $$$1$$$, $$$2$$$ in this order. Then we had possible operations of type $$$2$$$ before the first of these operations and operations of types $$$1$$$ and $$$3$$$ are applied to the different blocks. Thus we can make the same operations in the order $$$1$$$, $$$2$$$, $$$3$$$, $$$2$$$ and don't change the answer (we don't care what block to we apply the type $$$2$$$ operation). So there is an optimal sequence of operations without consecutive operations $$$3$$$, $$$2$$$, $$$1$$$, $$$2$$$.
Well, we know much enough about operations of types $$$2$$$ and $$$3$$$. Now let's go to the operation of type $$$1$$$. When we will start making operations of type $$$3$$$? There are two cases: we cannot make any operation of type $$$1$$$ or we have no possible operations of type $$$2$$$. In the first case we will make all possible operations of type $$$1$$$ so it doesn't matter in what order we will do them. In the second case we will never come back to the operations of type $$$1$$$ except the last operation, so we should prepare as much blocks of length $$$1$$$ as possible. The best way to do this is to remove zeroes from the shortest block except the corner blocks on each operation, and then remove zeroes from the corner blocks.
I claim that this is enough to solve the problem. It seems that there are too many cases but all of them are covered by the algorithm below.
Let's fix the parity of the first operation type to simplify the implementation, so on each step we will know the parity of the type of operation we should do next.
Now the algorithm is (after each operation we should try to update the answer):
• If we should do the operation of type $$$2$$$:   If we can do it, we do it.  Otherwise, we should terminate.
• If we can do it, we do it.
• Otherwise, we should terminate.
• If we should do the operation of type $$$1$$$ or $$$3$$$:   If there are no possible operations of type $$$2$$$:   If we can do operation of type $$$1$$$, we should try to do it (but don't actually do it) and update the answer. It it the last operation in this case.  If we can do operation of type $$$3$$$ and remove one of the center blocks, we should do it.  Otherwise, we should terminate.   If there are possible operations of type $$$2$$$:   If we can do operation of type $$$1$$$ on one of the middle blocks, we should do it on the one of the shortest middle blocks.  Otherwise, if we can do operation of type $$$1$$$ on one of the corner blocks, we should do it.  Otherwise, if we can do operation of type $$$3$$$ on one of the middle blocks, we should do it.  Otherwise, if we can do operation of type $$$3$$$ on one of the corner blocks, we should do it.  Otherwise, we should terminate.
• If there are no possible operations of type $$$2$$$:   If we can do operation of type $$$1$$$, we should try to do it (but don't actually do it) and update the answer. It it the last operation in this case.  If we can do operation of type $$$3$$$ and remove one of the center blocks, we should do it.  Otherwise, we should terminate.
• If we can do operation of type $$$1$$$, we should try to do it (but don't actually do it) and update the answer. It it the last operation in this case.
• If we can do operation of type $$$3$$$ and remove one of the center blocks, we should do it.
• Otherwise, we should terminate.
• If there are possible operations of type $$$2$$$:   If we can do operation of type $$$1$$$ on one of the middle blocks, we should do it on the one of the shortest middle blocks.  Otherwise, if we can do operation of type $$$1$$$ on one of the corner blocks, we should do it.  Otherwise, if we can do operation of type $$$3$$$ on one of the middle blocks, we should do it.  Otherwise, if we can do operation of type $$$3$$$ on one of the corner blocks, we should do it.  Otherwise, we should terminate.
• If we can do operation of type $$$1$$$ on one of the middle blocks, we should do it on the one of the shortest middle blocks.
• Otherwise, if we can do operation of type $$$1$$$ on one of the corner blocks, we should do it.
• Otherwise, if we can do operation of type $$$3$$$ on one of the middle blocks, we should do it.
• Otherwise, if we can do operation of type $$$3$$$ on one of the corner blocks, we should do it.
• Otherwise, we should terminate.
It covers all the cases and works in $$$\mathcal{O}(n)$$$. Total complexity is $$$\mathcal{O}(n \log n)$$$ because of sorting.
Bonus: $$$s$$$ is given, calculate answers for $$$q$$$ queries with $$$a$$$, $$$b$$$, $$$c$$$ faster than in $$$\mathcal{O}(nq)$$$.