$N$ 个排成一排的石头从左到右依次编号为 $1$ 到 $N$。每个石头的颜色要么是白色，要么是黑色。第 $i$ 个石头的重量为 $A_i$。

你将每次取走一个石头，直到所有石头都被取走，共进行 $N$ 次操作。

在取走一个石头时，如果该石头不是当前剩余石头中最左边或最右边的石头，且与该石头相邻的两个石头的颜色都与该石头的颜色不同，你将获得等同于该石头重量的分数。两个石头相邻是指它们之间没有其他未被取走的石头。

请寻找一种取走石头的顺序，使得获得的总分数最大。

输入格式

第一行包含一个正整数 $N$（$1 \le N \le 300\,000$）。

第二行包含一个长度为 $N$ 且仅由 B 和 W 组成的字符串 $S$。$S$ 的第 $i$ 个字符 $S_i$ 表示从左往右数第 $i$ 个石头的颜色。B 表示黑色，W 表示白色。

第三行包含 $N$ 个整数 $A_1, A_2, \cdots, A_N$（$1 \le A_i \le 10^9$），其中 $A_i$ 表示第 $i$ 个石头的重量。

输出格式

输出一行一个整数，表示采用最优策略取走石头时能获得的最大分数。

样例

输入格式 1

4
WBWB
6 4 5 3

输出格式 1

5

输入格式 2

8
WBBWBWBB
6 4 8 2 5 3 1 5

输出格式 2

13

说明

对于样例 2，如果按照初始位置从左到右的顺序，依次取走第 $5, 6, 2, 3, 4, 7, 8, 1$ 个石头，那么在取走第 $3$ 个和第 $5$ 个石头时会获得分数，总得分为 $13$ 分。