Strange Instructions solution codeforces
Dasha hascoins. Recently, she found a binary string of length and some operations that allows to change this string (she can do each operation any number of times):
- Replace substring 00 of by 0 and receive coins.
- Replace substring 11 of by 1 and receive coins.
- Remove 0 from any position in and pay 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 – 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( ) — the number of test cases.
The first line of each test case contains four integers, , , ( ).
The second line of each test case contains a binary stringof length .
It is guaranteed that the total sum ofover all test cases doesn’t exceed .
For each test case print the answer.
3 5 2 2 1 01101 6 4 3 5 110001 6 3 2 1 011110
3 11 4
In the first test case one of the optimal sequences of operations is 01101 0101 011 01. This sequence of operations consists of operations , and in this order. It satisfies all rules and gives profit . It can be shown that it is impossible to achieve higher profit in this test case, so the answer is .
In the second test case one of the optimal sequences of operations is 110001 11001 1001 101.
In the third test case one of the optimal sequences of operations is 011110 01110 1110 110 11 1.