Strange Instructions
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):  Replace substring 00 of $$$s$$$ by 0 and receive $$$a$$$ coins.  Replace substring 11 of $$$s$$$ by 1 and receive $$$b$$$ coins.  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.
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.
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.
from copy import copy
import sys
fin = sys.stdin

def start_from_1(count_moves_1_glue, count_moves_2, a, b, c):
    profit = 0
    if b > c:
        minimal_1 = 0
    else:
        minimal_1 = 1
    while count_moves_1_glue and count_moves_1_glue[-1] <= minimal_1:
        count_moves_1_glue.pop()
    while True:
        if not count_moves_1_glue:
            return profit
        can_glue = len(count_moves_1_glue) > 2
        assert count_moves_1_glue[-1] >= 1
        assert count_moves_2 >= 0
        if len(count_moves_1_glue) == 2:
            count_moves_1_glue = sorted(count_moves_1_glue)
        count_moves_1_glue[-1] -= 1
        if count_moves_1_glue[-1] > 0:
            profit += a
        else:
            if count_moves_2 == 0 and (not can_glue):
                return profit
            profit -= c
        while count_moves_1_glue and count_moves_1_glue[-1] <= minimal_1:
            can_glue = len(count_moves_1_glue) > 2
            if minimal_1 == 0 and can_glue:
                count_moves_2 += 1
            count_moves_1_glue.pop()
        if count_moves_2 == 0:
            return profit
        else:
            count_moves_2 -= 1
            profit += b

def solve(a, b, c, s):
    count_moves_1 = [0]
    count_moves_2 = 0
    for (c0, c1) in zip(s, s[1:]):
        if c0 == '1' and c1 == '1':
            count_moves_2 += 1
    if s[0] == '1':
        count_moves_1.append(0)
    for char in s:
        if char == '0':
            count_moves_1[-1] += 1
        elif char == '1' and count_moves_1[-1] > 0:
            count_moves_1.append(0)
    count_moves_1_glue = sorted([count_moves_1[0], count_moves_1[-1]]) + sorted(count_moves_1[1:-1], reverse=True)
    options = [0, start_from_1(copy(count_moves_1_glue), count_moves_2, a, b, c)]
    if count_moves_2 > 0:
        count_moves_2 -= 1
        options.append(b + start_from_1(count_moves_1_glue, count_moves_2, a, b, c))
    return max(options)

def operations(a, b, c, s, operation):
    if operation == 0:
        for index in range(len(s) - 1):
            if s[index:index + 2] == '11':
                yield (s[:index] + s[index + 1:], 1 - operation, b)
    if operation == 1:
        for index in range(len(s) - 1):
            if s[index:index + 2] == '00':
                yield (s[:index] + s[index + 1:], 1 - operation, a)
        for index in range(len(s)):
            if s[index:index + 1] == '0':
                yield (s[:index] + s[index + 1:], 1 - operation, -c)
max_score = dict()

def solve_slow_recursive(a, b, c, s, operation):
    k = (s, operation, a, b, c)
    if k in max_score:
        return max_score[k]
    options = [add_score + solve_slow_recursive(a, b, c, new_s, new_operation) for (new_s, new_operation, add_score) in operations(a, b, c, s, operation)]
    max_score[k] = max(options + [0])
    return max_score[k]

def solve_slow(a, b, c, s):
    alternatives = [solve_slow_recursive(a, b, c, s, operation) for operation in [0, 1]]
    return max(alternatives)

def local_test():
    a = 1
    b = 20
    c = 10
    for i in range(1, 10):
        for j in range(2 ** i):
            s = format(j, f'0{i}b')
            answer = solve(a, b, c, s)
            answer_correct = solve_slow(a, b, c, s)
            assert answer == answer_correct, f'{s}, {answer} != {answer_correct}'
t = int(fin.readline())
for test in range(t):
    (n, a, b, c) = map(int, fin.readline().split())
    s = fin.readline().rstrip('\n')
    answer = solve(a, b, c, s)
    print(answer)
import sys
I = lambda : [*map(int, sys.stdin.readline().split())]
(t,) = I()
for _ in range(t):
    (n, a, b, c) = I()
    s = input()
    start = int(s[0])
    curr = s[0]
    ind = 0
    blocks = []
    for i in range(1, n):
        if s[i] != curr:
            blocks.append(i - ind)
            curr = s[i]
            ind = i
    blocks.append(n - ind)
    l = len(blocks)
    zero = 0
    one = 0
    for i in range(l):
        if i % 2 == start:
            zero += blocks[i] - 1
        else:
            one += blocks[i] - 1
    if c > b:
        val = (a + b) * min(zero, one)
        if zero > one:
            print(val + a)
        elif one > zero:
            print(val + b)
        else:
            print(val)
    else:
        zeroes = [blocks[i] for i in range(l) if i % 2 == start and i > 0 and (i < l - 1)]
        zeroes.sort()
        extra = 0
        xxtra = 0
        if start == 0:
            extra += blocks[0] - 1
            xxtra += 1
        if (l - 1) % 2 == start:
            extra += blocks[-1] - 1
            xxtra += 1
        z1 = zeroes[:]
        extra1 = extra
        xxtra1 = xxtra
        val1 = 0
        ind = 0
        for i in range(one):
            while ind < len(zeroes) and zeroes[ind] == 1:
                ind += 1
            if ind < len(zeroes):
                zeroes[ind] -= 1
                val1 += a
            elif extra > 0:
                extra -= 1
                val1 += a
            elif xxtra > 0:
                xxtra -= 1
                val1 -= c
            else:
                break
            val1 += b
        val1 += (b - c) * zeroes.count(1)
        if len(zeroes) > 0 and max(zeroes) > 1 or extra > 0:
            val1 += a
        val2 = 0
        ind = 0
        for i in range(one):
            val2 += b
            if i == one - 1:
                break
            while ind < len(zeroes) and z1[ind] == 1:
                ind += 1
            if ind < len(z1):
                z1[ind] -= 1
                val2 += a
            elif extra1 > 0:
                extra1 -= 1
                val2 += a
            elif xxtra1 > 0:
                xxtra1 -= 1
                val2 -= c
            else:
                break
        val2 += (b - c) * z1.count(1)
        print(max(val1, val2))
import sys
input = sys.stdin.readline
out = []
ssl = []
t = int(input())
for _ in range(t):
    (n, a, b, c) = map(int, input().split())
    s = input().strip()
    ssl.append(s)
    z = [0]
    zc = 0
    oc = 0
    for ch in s:
        if ch == '0':
            z[-1] += 1
            zc += 1
        else:
            z.append(0)
            oc += 1
    M1 = sum((max(0, v - 1) for v in z))
    if len(z) == 1:
        out.append(a if n >= 2 else 0)
        continue
    l = z.pop(0)
    r = z.pop()
    poss = [0]
    zz = sorted(z)[::-1]
    curr = 0
    L1 = M1
    L2 = 0
    Z1 = 0
    OL = oc
    ZL = zc
    while zz and zz[-1] == 0:
        zz.pop()
        L2 += 1
    while zz and zz[-1] == 1:
        zz.pop()
        Z1 += 1
    while True:
        if ZL == 0:
            break
        if L1 > 0:
            poss.append(curr + a)
        if OL <= 1:
            break
        if L2 > 0:
            if L1 > 0:
                curr += a
                ZL -= 1
                L1 -= 1
                if zz:
                    zz[-1] -= 1
                    if zz[-1] == 1:
                        zz.pop()
                        Z1 += 1
                curr += b
                L2 -= 1
                OL -= 1
            else:
                curr -= c
                ZL -= 1
                curr += b
                OL -= 1
        else:
            ZL -= 1
            if Z1 == 0:
                break
            Z1 -= 1
            curr -= c
            OL -= 1
            curr += b
        poss.append(curr)
    zz = sorted(z)[::-1]
    curr = 0
    L1 = M1
    L2 = 0
    Z1 = 0
    OL = oc
    ZL = zc
    while zz and zz[-1] == 0:
        zz.pop()
        L2 += 1
    while zz and zz[-1] == 1:
        zz.pop()
        Z1 += 1
    good = False
    if L2:
        OL -= 1
        L2 -= 1
        curr = b
        poss.append(b)
        good = True
    while good:
        if ZL == 0:
            break
        if L1 > 0:
            poss.append(curr + a)
        if OL <= 1:
            break
        if L2 > 0:
            if L1 > 0:
                curr += a
                ZL -= 1
                L1 -= 1
                if zz:
                    zz[-1] -= 1
                    if zz[-1] == 1:
                        zz.pop()
                        Z1 += 1
                curr += b
                L2 -= 1
                OL -= 1
            else:
                curr -= c
                ZL -= 1
                curr += b
                OL -= 1
        else:
            ZL -= 1
            if Z1 == 0:
                break
            Z1 -= 1
            curr -= c
            OL -= 1
            curr += b
        poss.append(curr)
    out.append(max(poss))
print('\n'.join(map(str, out)))