D. Right Left Wrong
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Влад нашёл полоску из $$$n$$$ клеток, пронумерованных слева направо от $$$1$$$ до $$$n$$$. На $$$i$$$-й клетке записаны положительное целое число $$$a_i$$$ и буква $$$s_i$$$, все $$$s_i$$$ равны либо 'L' либо 'R'.

Влад предлагает вам попробовать набрать максимально возможное количество очков, сделав любое (возможно нулевое) количество операций.

За одну операцию вы можете выбрать два индекса $$$l$$$ и $$$r$$$ ($$$1 \le l < r \le n$$$), такие что $$$s_l$$$ = 'L' и $$$s_r$$$ = 'R' и сделать следующее:

  • прибавить к текущему счёту $$$a_l + a_{l + 1} + \dots + a_{r - 1} + a_r$$$ очков;
  • заменить $$$s_i$$$ на '.' для всех $$$l \le i \le r$$$, то есть выбирать эти индексы вы больше не сможете.

Для примера рассмотрим следующую полоску:

$$$3$$$$$$5$$$$$$1$$$$$$4$$$$$$3$$$$$$2$$$
LRLLLR

Можно сначала выбрать $$$l = 1$$$, $$$r = 2$$$ и добавить к своему счёту $$$3 + 5 = 8$$$

$$$3$$$$$$5$$$$$$1$$$$$$4$$$$$$3$$$$$$2$$$
..LLLR

Затем выбрать $$$l = 3$$$, $$$r = 6$$$ и прибавить к счёту $$$1 + 4 + 3 + 2 = 10$$$

$$$3$$$$$$5$$$$$$1$$$$$$4$$$$$$3$$$$$$2$$$
......

В результате невозможно выполнить ещё одну операцию, а итоговый счёт равен $$$18$$$.

Какой максимальный счёт можно набрать?

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

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

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — длину полоски.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — числа, записанные на полоске.

Третья строка каждого набора содержит строку $$$s$$$ из $$$n$$$ символов 'L' и 'R'.

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

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

Для каждого набора входных данных выведите одно целое число — максимальное возможное количество очков, которое можно набрать.

Пример
Входные данные
4
6
3 5 1 4 3 2
LRLLLR
2
2 8
LR
2
3 9
RL
5
1 2 3 4 5
LRLRR
Выходные данные
18
10
0
22