Монокарп очень долго коллекционировал разные журналы и теперь решил их продать. Для этого он выставил в ряд $$$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$$$.
На каждый набор входных данных выведите максимальное количество журналов, которые Монокарп может спасти от дождя.
450111010 5 8 9 6601101120 10 9 30 20 1940000100 100 100 100401115 4 5 1
27 80 0 14
В первом наборе входных данных в примере нужно переместить крышку со второй коробки влево на первую коробку. Тогда коробки $$$1$$$, $$$3$$$ и $$$4$$$ будут накрыты крышками, и $$$10 + 8 + 9 = 27$$$ журналов будут спасены от дождя.
Во втором наборе входных данных нужно переместить крышку со второй коробки на первую коробку, крышку с третьей коробки на вторую коробку, крышку с пятой коробки на четвертую коробку, крышку с шестой коробки на пятую коробку. Тогда коробки $$$1$$$, $$$2$$$, $$$4$$$ и $$$5$$$ будут накрыты крышками, и $$$20 + 10 + 30 + 20 = 80$$$ журналов будут спасены от дождя.
В третьем наборе входных данных нет ни одной крышки, поэтому ни один из журналов нельзя спасти от дождя.
Название |
---|