有 $N$ 顆石頭排成一列，編號為 $1$ 到 $N$。每顆石頭的顏色不是白色就是黑色。第 $i$ 顆石頭的重量為 $A_i$。

你將每次取走一顆石頭，直到所有石頭都被取走為止。

當取走一顆石頭時，如果該石頭不是目前剩餘石頭中最左邊或最右邊的石頭，且與該石頭相鄰的兩顆石頭顏色都與它不同，你就可以獲得等同於該石頭重量的分數。如果兩顆石頭之間沒有其他石頭，則稱它們是相鄰的。

請尋找一種取走石頭的方法，使得獲得的總分最大。

輸入格式

第一行包含一個正整數 $N$ ($1 \le N \le 300000$)。

第二行包含一個長度為 $N$ 的字串 $S$，其中每個字元皆為 B 或 W。$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

說明

若依序取走初始位置從左數來第 5, 6, 2, 3, 4, 7, 8, 1 顆石頭，則在取走編號 3 和編號 5 的石頭時可以獲得分數，總共獲得 13 分。