Strange Instructions solution codeforces

Strange Instructions solution codeforces

 

Dasha has 1010010100 coins. Recently, she found a binary string ss of length nn and some operations that allows to change this string (she can do each operation any number of times):

  1. Replace substring 00 of ss by 0 and receive aa coins.
  2. Replace substring 11 of ss by 1 and receive bb coins.
  3. Remove 0 from any position in ss and pay cc 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 1133 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 Strange Instructions solution codeforces

The first line contains a single integer tt (1t1041≤t≤104) — the number of test cases.

The first line of each test case contains four integers nnaabbcc (1n105,1a,b,c1091≤n≤105,1≤a,b,c≤109).

The second line of each test case contains a binary string ss of length nn.

It is guaranteed that the total sum of nn over all test cases doesn’t exceed 21052⋅105.

Output Strange Instructions solution codeforces

For each test case print the answer.

Example

input

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

output

Copy
3
11
4
Note Strange Instructions solution codeforces

In the first test case one of the optimal sequences of operations is 01101  0101  011  01. This sequence of operations consists of operations 2233 and 22 in this order. It satisfies all rules and gives profit 33. It can be shown that it is impossible to achieve higher profit in this test case, so the answer is 33.

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.

Leave a Comment

Your email address will not be published.