시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)50618116440.394%

문제

$N$ 개의 돌이 일렬로 나열되어 있다. 각 돌은 흰색 또는 검은색의 색상을 갖는다. 

돌들을 왼쪽부터 1번 돌, 2번 돌,$\cdots$, $N$번 돌이라 하자. $i$번째 돌의 무게는 $A_i$이다.

당신은 나열된 돌들 중 하나를 골라 가져가는 것을 모든 돌이 없어질 때까지 총 $N$번 반복하려고 한다.

돌을 가져갈 때, 만약 그 돌이 현재 나열된 돌 중 가장 왼쪽이나 가장 오른쪽이 아니며, 가져간 돌에 인접한 두 돌 모두 가져간 돌과 다른 색인 경우 당신은 가져간 돌의 무게만큼의 점수를 얻는다.

가장 많은 점수를 얻을 수 있도록 돌을 가져가는 방법을 구하여라.

입력

첫 줄에 양의 정수 $N$이 주어진다. ($1 \le N \le 3 \times 10^5$)

둘째 줄에 B 또는 W로만 이루어진 길이 $N$의 문자열 $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

8
WBBWBWBB
6 4 8 2 5 3 1 5

예제 출력 1

13

노트

처음 위치 기준 왼쪽에서 $5,\ 6,\ 2,\ 3,\ 4,\ 7,\ 8,\ 1$번째 돌을 순서대로 가져가면 $3$번째 돌과 $5$번째 돌을 가져갈 때 점수를 얻어 $13$점이 된다.