2022综合复习赛一 : 六年级

P7 : 六年级

描述

有一列 $n$ 个方格，每个方格被涂成红色或蓝色，每个方格上面有一个数字 $a_i$ 。

从方格中按如下规则从前到后依次取出一些数，使得这些数的和最大，这个最大值是多少？

1、相邻的两个数之和为奇数。

2、相邻的两个数所在的格子颜色不能相同。

输入

第一行， $n$ 。

第二行， $n$ 个 $a_i$ 。

第三行，长度为 $n$ 由 $R、B$ 构成的字符串。

对于100%的数据：

$1\le n \le 2×10^5$ ；

$1\le a_i \le 10^9$ 。

输出

一个整数，表示能得到的最大值。

样例

5
11 3 4 6 5
BBBRR

5
1 3 3 6 5
BRRBR