在一张纸条上画了一行$$$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$$$。
输出
对于每个测试用例,打印一个整数 - 如果允许您执行任意数量的操作(包括零),则可以获得的最高分数。
示例
输入复制
53<>>5 4 65<><>>5 -2 4 -3 72>>-1 -28>>>><<<<1 -1 1 -1 1 -1 1 -15><<<>-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$$$。