C. Журналы Монокарпа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп очень долго коллекционировал разные журналы и теперь решил их продать. Для этого он выставил в ряд $$$n$$$ коробок с журналами, причем в $$$i$$$-й коробке находится $$$a_i$$$ журналов. Некоторые из коробок он накрыл крышками.

Внезапно пошел дождь, и Монокарпу нужно спасти от дождя как можно большее количество журналов. Для этого он может сделать следующее: если коробка $$$i$$$ изначально была накрыта крышкой, он может либо переместить крышку с коробки $$$i$$$ на коробку $$$(i-1)$$$ (если она есть), либо оставить крышку на коробке $$$i$$$. Считайте, что все перемещения крышек Монокарп выполнит мгновенно, и каждая крышка будет перемещена не более одного раза. Журналы, которые после перемещения будут находиться в коробках с крышками, будут спасены от дождя; все остальные журналы намокнут.

Перед вами стоит задача определить максимальное количество журналов, которые Монокарп может спасти от дождя.

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

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

В первой строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество коробок с журналами.

Во второй строке записана строка, состоящая из $$$n$$$ символов 0 и/или 1. Если $$$i$$$-й символ строки равен 1, то изначально $$$i$$$-я коробка накрыта крышкой. Если $$$i$$$-й символ строки равен 0, то изначально $$$i$$$-я коробка не накрыта крышкой.

В третьей строке записана последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^4$$$), где $$$a_i$$$ равно количеству журналов в $$$i$$$-й коробке.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

На каждый набор входных данных выведите максимальное количество журналов, которые Монокарп может спасти от дождя.

Пример
Входные данные
4
5
01110
10 5 8 9 6
6
011011
20 10 9 30 20 19
4
0000
100 100 100 100
4
0111
5 4 5 1
Выходные данные
27
80
0
14
Примечание

В первом наборе входных данных в примере нужно переместить крышку со второй коробки влево на первую коробку. Тогда коробки $$$1$$$, $$$3$$$ и $$$4$$$ будут накрыты крышками, и $$$10 + 8 + 9 = 27$$$ журналов будут спасены от дождя.

Во втором наборе входных данных нужно переместить крышку со второй коробки на первую коробку, крышку с третьей коробки на вторую коробку, крышку с пятой коробки на четвертую коробку, крышку с шестой коробки на пятую коробку. Тогда коробки $$$1$$$, $$$2$$$, $$$4$$$ и $$$5$$$ будут накрыты крышками, и $$$20 + 10 + 30 + 20 = 80$$$ журналов будут спасены от дождя.

В третьем наборе входных данных нет ни одной крышки, поэтому ни один из журналов нельзя спасти от дождя.