Вам назначили задачу проложить газопровод вдоль дороги. Для простоты будем считать, что дорога — это отрезок $$$[0, n]$$$ на оси $$$OX$$$. На дороге может быть несколько перекрестков, но для простоты будем считать каждый перекресток как интервал $$$(x, x + 1)$$$ для некоторого целого $$$x$$$. Таким образом, можно представить дорогу как двоичную строку, состоящую из $$$n$$$ символов, где цифра 0 означает, что текущий интервал не содержит перекресток, а 1 означает, что интервал содержит перекресток.
Обычно газопровод можно установить вдоль дороги на высоте $$$1$$$ вместе с поддерживающими его столбами в каждой целой точке (поэтому при установке вдоль дороги $$$[0, n]$$$ нам необходимо поставить $$$n + 1$$$ столб). Но на перекрестках нам необходимо поднять трубу на высоту $$$2$$$, чтобы она не мешала проезду машин.
Мы можем поднять или опустить трубу за счет вставки зигзагообразных частей. Каждый зигзаг можно представить как отрезок $$$[x, x + 1]$$$ с целым $$$x$$$, состоящий из трех частей: $$$0.5$$$ единицы горизонтальной трубы + $$$1$$$ единицы вертикальной трубы + $$$0.5$$$ горизонтальной. Заметьте, что если труба находится на высоте $$$2$$$, столбы, ее поддерживающие, также должны быть длины $$$2$$$.
Каждая единица длины газопровода стоит нам $$$a$$$ бурлей, а каждая единица длины столба — $$$b$$$ бурлей. Поэтому не всегда выгодно просто пустить трубопровод на высоте $$$2$$$. Определите форму трубопровода с минимальной возможной ценой, а также его цену.
Заметим, что вы обязаны начать и закончить трубу на высоте $$$1$$$, а также гарантируется, что первый и последний символы во входной строке обязательно равны 0.
В первой строке задано одно число $$$T$$$ ($$$1 \le T \le 100$$$) — количество независимых запросов. В следующих $$$2 \cdot T$$$ строках заданы запросы — один запрос на две строки.
В первой строке заданы три целых числа $$$n$$$, $$$a$$$, $$$b$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le a \le 10^8$$$, $$$1 \le b \le 10^8$$$) — длина дороги, цена за единицу длины трубы и цена за единицу длины столба, соответственно.
Во второй строке задана двоичная строка $$$s$$$ ($$$|s| = n$$$, $$$s_i \in \{0, 1\}$$$, $$$s_1 = s_n = 0$$$) — описание дороги.
Гарантируется, что суммарная длина строк $$$s$$$ во всех запросах не превосходит $$$2 \cdot 10^5$$$.
Выведите $$$T$$$ чисел — по одному на запрос. Для каждого запроса выведите минимальную возможную стоимость построенного трубопровода.
4 8 2 5 00110010 8 1 1 00110010 9 100000000 100000000 010101010 2 5 1 00
94 25 2900000000 13
Оптимальный газопровод для первого запроса изображен на рисунке сверху.
Оптимальный газопровод для второго запроса изображен ниже:
Оптимальный (и единственный) газопровод для третьего примера изображен ниже:
Оптимальный газопровод для четвертого примера изображен ниже:
