F. Странные инструкции
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Даши есть $$$10^{100}$$$ монет. Недавно она нашла бинарную строку $$$s$$$ длины $$$n$$$ и несколько операций, с помощью которых её можно изменять (каждую операцию можно делать сколько угодно раз):

  1. Заменить подстроку строки $$$s$$$, равную 00, на 0 и получить $$$a$$$ монет.
  2. Заменить подстроку строки $$$s$$$, равную 11, на 1 и получить $$$b$$$ монет.
  3. Удалить из строки $$$s$$$ символ 0, заплатив за это $$$c$$$ монет.

Оказалось, что при выполнении операций нужно соблюдать следующее правило:

  • Запрещается делать две операции с номерами одинаковой чётности подряд. Операции пронумерованы числами от $$$1$$$ до $$$3$$$ в порядке, в котором они даны выше.

Определите максимальное количество монет, которое Даша может получить делая эти операции и не нарушая правило.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следуют описания этих наборов.

В первой строке дано четыре целых числа $$$n$$$, $$$a$$$, $$$b$$$, $$$c$$$ ($$$1 \leq n \leq 10^5, 1 \leq a, b, c \leq 10^9$$$).

Во второй строке дана бинарная строка $$$s$$$ длины $$$n$$$.

Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите ответ.

Пример
Входные данные
3
5 2 2 1
01101
6 4 3 5
110001
6 3 2 1
011110
Выходные данные
3
11
4
Примечание

В первом наборе входных данных одна из оптимальных последовательностей операций такая: 01101 $$$\rightarrow$$$ 0101 $$$\rightarrow$$$ 011 $$$\rightarrow$$$ 01. Эта последовательность состоит из операций $$$2$$$, $$$3$$$ и $$$2$$$ в таком порядке. Она удовлетворяет всем правилам и даёт $$$3$$$ монеты. Можно показать, что нельзя получить больше монет, поэтому ответ $$$3$$$.

Во втором наборе входных данных одна из оптимальных последовательностей операций такая: 110001 $$$\rightarrow$$$ 11001 $$$\rightarrow$$$ 1001 $$$\rightarrow$$$ 101.

В третьем наборе входных данных одна из оптимальных последовательностей операций такая: 011110 $$$\rightarrow$$$ 01110 $$$\rightarrow$$$ 1110 $$$\rightarrow$$$ 110 $$$\rightarrow$$$ 11 $$$\rightarrow$$$ 1.