题目描述

有 $N$ 块石头排成一列，每块石头的颜色为白色或黑色。

从左到右将石头编号为 $1,2,\ldots,N$，第 $i$ 块石头的重量为 $A_i$。

你需要重复进行如下操作，直到所有石头都被取走：从当前仍排成一列的石头中任选一块并将其取走。总共会进行 $N$ 次操作。

取走一块石头时，若它满足以下两个条件，你将获得等于该石头重量的分数：

1. 它既不是当前最左端的石头，也不是当前最右端的石头；
2. 与它相邻的两块石头的颜色都与它不同。

请计算通过合理安排取石顺序，最多能够获得多少分。

输入格式

第一行包含一个正整数 $N$。$(1\le N\le 3\times 10^5)$

第二行包含一个长度为 $N$、仅由字符 B 和 W 组成的字符串 $S$。其中 $S_i$ 表示第 $i$ 块石头的颜色：B 表示黑色，W 表示白色。

第三行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$。$(1\le A_i\le 10^9)$

输出格式

输出一个整数，表示采用最优取石顺序时能够获得的最大分数。

样例

输入

8
WBBWBWBB
6 4 8 2 5 3 1 5

输出

13

样例说明

按照原始编号 $5,6,2,3,4,7,8,1$ 的顺序取走石头，可以在取走第 $3$ 块和第 $5$ 块石头时得分，总分为 $13$。