20220264 - 六年级
有一列n个方格，每个方格被涂成红色或蓝色，每个方格上面有一个数字a_i。
从方格中按如下规则从前到后依次取出一些数，使得这些数的和最大，这个最大值是多少？
1、相邻的两个数之和为奇数。
2、相邻的两个数所在的格子颜色不能相同。
Input
第一行，n。
第二行，n个a_i。
第三行，长度为n由R、B构成的字符串。
对于100%的数据：
1\le n \le 2×10^5；
1\le a_i \le 10^9。
Output
一个整数，表示能得到的最大值。
Examples
Input
5 11 3 4 6 5 BBBRR
Output
17
Input
5 1 3 3 6 5 BRRBR
Output
14