E. Раскрась стрелки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На полоске бумаги в ряд нарисованы $$$n$$$ стрелок, пронумерованных от $$$1$$$ до $$$n$$$. Каждая стрелка указывает либо налево, либо направо. Изначально все стрелки покрашены в синий цвет.

За одну операцию можно перекрасить стрелку синего цвета в красный цвет. Для первой операции можно выбрать любую стрелку. Для каждой следующей операции разрешается выбрать только такую стрелку, в направлении которой указывает стрелка, перекрашенная на прошлой операции. То есть, если на прошлой операции была перекрашена стрелка, указывающая налево, то для текущей операции необходимо выбрать стрелку на позиции с номером меньше предыдущей. Аналогично, если предыдущая стрелка указывала направо, то текущая должна находиться на позиции с большим номером, чем она. Обратите внимание, что не обязательно выбирать стрелку на соседней позиции.

У каждой стрелки есть награда за ее перекрашивание в красный цвет — некоторое целое число (возможно, отрицательное, положительное или ноль).

Итоговый счет — это сумма наград за перекрашенные стрелки. Какой максимальный счет можно набрать, если разрешается сделать любое количество операций (в том числе, ноль)?

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

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

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

Во второй строке записана строка, состоящая из $$$n$$$ символов '<' и/или '>' (ASCII коды 60 и 62, соответственно).

В третьей строке записаны $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$-10^9 \le c_i \le 10^9$$$) — награда за перекрашивание каждой стрелки.

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

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

На каждый набор входных данных выведите одно целое число — максимальный счет, который можно набрать, если разрешается сделать любое количество операций (в том числе, ноль).

Пример
Входные данные
5
3
<>>
5 4 6
5
<><>>
5 -2 4 -3 7
2
>>
-1 -2
8
>>>><<<<
1 -1 1 -1 1 -1 1 -1
5
><<<>
-1 100 100 100 100
Выходные данные
10
9
0
4
399
Примечание

В первом наборе входных данных можно сначала перекрасить стрелку на позиции $$$2$$$. Эта стрелка указывает направо, поэтому на следующей операции необходимо выбрать стрелку справа от нее. Перекрасим стрелку на позиции $$$3$$$. Эта стрелка тоже указывает направо, поэтому больше никаких стрелок перекрасить нельзя. Ответ равен $$$c_2 + c_3 = 4 + 6 = 10$$$.

Во втором наборе можно перекрасить стрелки $$$3$$$, затем $$$1$$$.

В третьем наборе наиболее выгодно не перекрашивать никаких стрелок. Это даст ответ $$$0$$$, когда перекрашивание хотя бы одной стрелки приведет к отрицательному ответу.

В четвертом наборе можно перекрасить стрелки в следующем порядке: $$$3, 7, 1, 5$$$.

В пятом наборе можно перекрасить стрелки в следующем порядке: $$$4, 3, 2, 1, 5$$$.