Description

Troy and JP are hockey fans. In this season, each hockey team plays $N$ games. Each game is played between two teams, and the team with the higher score wins. There are no ties.

Troy’s favorite team is the Waterloo Geese, and he recorded the result of each game for this team. The results are written as a string $S$. If the Geese won the $i$-th game, then $S_i=\texttt{W}$; otherwise, $S_i=\texttt{L}$. He also recorded that in the $i$-th game, they scored $A_i$ points.

JP’s favorite team is the Laurier Golden Hawks, and he also recorded the result of each game for this team. The results are written as a string $T$. If the Golden Hawks won the $j$-th game, then $T_j=\texttt{W}$; otherwise, $T_j=\texttt{L}$. He also recorded that in the $j$-th game, they scored $B_j$ points.

Troy and JP recorded, in order, the results and scores of every game played by their favorite teams.

A crosstown derby means a game between the Waterloo Geese and the Laurier Golden Hawks (because both teams’ home arenas are in Waterloo). Since Troy and JP did not record the opponents in their favorite teams’ games, they cannot determine whether any crosstown derbies happened, nor which games were crosstown derbies. They want to know, based on the information they recorded, what the maximum possible total sum of points scored by both teams across all crosstown derbies is.

Input Format

The first line contains an integer $N$.

The second line contains a string $S$ of length $N$, and it is guaranteed that $S$ contains only $\texttt{W}$ and $\texttt{L}$.

The third line contains $N$ integers $A_1,\ldots ,A_N$.

The fourth line contains a string $T$ of length $N$, and it is guaranteed that $T$ contains only $\texttt{W}$ and $\texttt{L}$.

The fifth line contains $N$ integers $B_1,\ldots ,B_N$.

Output Format

Output one line containing one integer, meaning the maximum possible total sum of points scored by both teams across all crosstown derbies.

1
W
2
W
3

0

4
WLLW
1 2 3 4
LWWL
6 5 3 2

14

Hint

Sample Explanation

Sample 1 Explanation

Because both teams won their games, there cannot be any crosstown derbies.

Sample 2 Explanation

The 4th game played by each team could be a crosstown derby: the Geese scored $4$ points and the Golden Hawks scored $2$ points. The Geese’s 3rd game and the Golden Hawks’ 2nd game could also be a crosstown derby: the Golden Hawks scored $5$ points and the Geese scored $3$ points. The total sum of points is $4 + 2 + 5 + 3 = 14$, and this is the maximum possible total.

Note that the Geese won their 1st game and scored $1$ point, so that game cannot be against the Golden Hawks, because the Golden Hawks have no game where they scored $0$ points. Also, the Golden Hawks’ 1st game cannot be a crosstown derby either, because the Golden Hawks lost their 1st game and scored $6$ points, and the Geese never had a game where they scored at least $7$ points.

Constraints

For $100\%$ of the testdata, it is guaranteed that $1\le N\le 10^3$, $1\le A_i,B_i\le 10^6$, $S_i,T_i\in\{$W, L$\}$.

• Subtask 1 ($40$ points): $N\le 10$ is guaranteed.
• Subtask 2 ($60$ points): No additional constraints.

Notes

This problem is translated from Canadian Computing Olympiad 2020 Day 1 T1 Geese vs. Hawks.

Translated by ChatGPT 5