Geese vs. Hawks
Troy 和 JP 是冰球的忠实粉丝。本赛季每支球队都进行了 $N$ 场比赛。每场比赛都在两支球队之间进行，得分较高的球队获胜。没有比赛以平局告终。
Troy 最喜欢的球队是 Waterloo Geese，他将他们所有比赛的结果记录为一个字符串 $S$。如果 Geese 在第 $i$ 场比赛中获胜，则 $S_i = \text{W}$；否则，如果 Geese 在第 $i$ 场比赛中失败，则 $S_i = \text{L}$。他还记录了他们在第 $i$ 场比赛中的得分 $A_i$。
JP 最喜欢的球队是 Laurier Hawks，他将他们所有比赛的结果记录为一个字符串 $T$。如果 Hawks 在第 $j$ 场比赛中获胜，则 $T_j = \text{W}$；否则，如果 Hawks 在第 $j$ 场比赛中失败，则 $T_j = \text{L}$。他还记录了他们在第 $j$ 场比赛中的得分 $B_j$。
Troy 和 JP 按照他们各自支持的球队比赛的顺序记录了胜负和得分。
“宿敌之战”是指 Geese 和 Hawks 互相对战的比赛。由于 Troy 和 JP 都没有记录他们支持的球队面对的对手，他们不确定哪些比赛（如果有的话）是宿敌之战。他们想知道，在符合他们所记录信息的前提下，宿敌之战中两队得分之和的最大可能值是多少。
输入格式
第一行包含一个整数 $N$ ($1 \le N \le 1000$)。
第二行包含一个长度为 $N$ 的字符串 $S$，由字符 $\text{W}$ 和 $\text{L}$ 组成。
第三行包含 $N$ 个整数 $A_1, \dots, A_N$ ($1 \le A_i \le 1\,000\,000$)。
第四行包含一个长度为 $N$ 的字符串 $T$，由字符 $\text{W}$ 和 $\text{L}$ 组成。
第五行包含 $N$ 个整数 $B_1, \dots, B_N$ ($1 \le B_j \le 1\,000\,000$)。
在 25 分的总分中，有 10 分满足 $N \le 10$。
输出格式
输出一行一个整数，表示潜在的宿敌之战中两队得分之和的最大可能值。
样例
样例输入 1
1 W 2 W 3
样例输出 1
0
说明 1
由于 Geese 和 Hawks 都赢了他们所有的比赛，因此不可能有任何宿敌之战。
样例输入 2
4 WLLW 1 2 3 4 LWWL 6 5 3 2
样例输出 2
14
说明 2
每支球队进行的第四场比赛可能是一场宿敌之战，其中 Geese 以 4 分对 Hawks 的 2 分获胜。Geese 进行的第三场比赛和 Hawks 进行的第二场比赛可能是一场宿敌之战，其中 Hawks 以 5 分对 Geese 的 3 分获胜。两队得分之和为 $4 + 2 + 5 + 3 = 14$，这是最大可能值。
注意，Geese 进行的第一场比赛是一场获胜且得分为 1 分的比赛：这场比赛不可能是对阵 Hawks 的，因为没有一场比赛是 Hawks 得分为 0 分的。同样，Hawks 进行的第一场比赛也不能使用，因为 Hawks 输了且得了 6 分，而 Geese 从未有过得分至少为 7 分的比赛。
Wrong Answer
Troy 为一场编程竞赛出了以下题目（标题为 WA）：
有一个包含 $N$ 个关卡的游戏，编号从 1 到 $N$。有两个角色，最初都在第 1 关。对于 $i < j$，将一个角色从第 $i$ 关移动到第 $j$ 关需要花费 $A_{i,j}$ 个金币。不允许将角色从第 $i$ 关移动到第 $j$ 关（其中 $i > j$）。为了赢得游戏，每个关卡（第 1 关除外）必须恰好被一个角色访问。赢得游戏所需的最少金币数量是多少？
JP 是一名参赛者，提交了以下 Python 解法：
def Solve(N, A):
# A[i][j] is cost of moving from level i to level j
# N is the number of levels
x, y, sx, sy = 1, 1, 0, 0 # Initialize x and y to 1, sx and sy to 0
for i in range(2, N + 1): # loop from 2 to N
if sx + A[x][i] < sy + A[y][i]:
sx += A[x][i]
x = i
else:
sy += A[y][i]
y = i
return sx + syTroy 确信 JP 的解法是错误的。假设对于 WA 的某个输入，JP 的解法返回 $X$，但赢得游戏所需的最少金币数量为 $Y$。为了展示 JP 的解法有多么错误，请帮助 Troy 找到一个输入 $N$ 和 $A_{i,j}$，使得 $\frac{X}{Y}$ 最大化。
输入格式
无输入。
输出格式
按以下格式输出一个 WA 的输入：
第一行输出一个整数 $N$ ($2 \le N \le 100$)。
然后输出 $N-1$ 行；第 $i$ 行应包含 $N-i$ 个整数 $A_{i,i+1}, \dots, A_{i,N}$ ($1 \le A_{i,j} \le 100$)。
如果输出格式不正确，将在评测系统的样例测试中获得错误判定并得 0 分。
否则，假设对于你的输入，JP 的解法返回 $X$，而赢得游戏所需的最少金币数量为 $Y$。你将获得 $\lfloor \min(25, \frac{X}{4Y}) \rfloor$ 分，其中 $\lfloor Z \rfloor$ 是不大于 $Z$ 的最大整数。
样例
样例输出
5 1 2 3 4 10 9 8 7 6 5
说明
赢得游戏的最佳方式是一个角色访问第 2 关，另一个角色访问第 3、4 和 5 关。这花费了 $(1) + (2 + 7 + 5) = 15$ 个金币。JP 的解法返回 18。因此 $\frac{X}{4Y} = \frac{18}{4 \times 15} = 0.3$，所以该输出将获得 $\lfloor 0.3 \rfloor = 0$ 分。
Fun Palace
你正在努力为你的朋友们准备一场有趣的派对。幸运的是，你刚刚找到了派对的完美场地：一个趣味宫殿。趣味宫殿有 $N$ 个趣味房间，以线性结构连接。趣味房间编号从 1 到 $N$，对于 $1 \le i \le N-1$，趣味房间 $i$ 和 $i+1$ 由一个趣味隧道连接。我们称这样的趣味隧道与趣味房间 $i$ 和 $i+1$ 相关联。此外，趣味房间 1 与一个离开趣味宫殿的出口隧道相关联。
趣味隧道可以处于两种状态之一：开启或关闭。当房间 $i$ 和 $i+1$ 之间的趣味隧道开启时，朋友们可以在两个房间之间自由往返。
默认情况下，所有趣味隧道都是关闭的。但是，它们可以由一组朋友按下所需数量的趣味按钮来暂时开启。对于每个趣味隧道，在与该隧道相连的趣味房间中都有一组趣味按钮。如果连接到隧道的其中一个房间中的所有按钮都被不同的朋友按下，那么趣味隧道就会开启。否则，趣味隧道将立即关闭。房间 $i$ 和 $i+1$ 之间的趣味隧道连接到房间 $i$ 中的一组 $a_i$ 个按钮和房间 $i+1$ 中的一组 $b_i$ 个按钮。换句话说，如果房间 $i$ 中至少有 $a_i$ 个朋友，或者房间 $i+1$ 中至少有 $b_i$ 个朋友，那么房间 $i$ 和 $i+1$ 之间的隧道就可以开启。
出口隧道遵循类似的规则，但它仅连接到房间 1 中存在的一组 $e$ 个按钮。
你希望确保你的朋友们获得最大的乐趣，这显然意味着要让你的朋友们永远被困在趣味宫殿里。在出口趣味隧道永远不会开启的前提下，你可以分配到各个趣味房间的朋友的最大数量是多少？
输入格式
第一行包含一个整数 $N$ ($1 \le N \le 1000$)，即趣味房间的数量。
第二行包含一个整数 $e$ ($1 \le e \le 10\,000$)。
接下来的 $N-1$ 行，每行包含两个空格分隔的整数，其中第 $i$ 行包含 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le 10\,000$)。
在 25 分的总分中，有 3 分满足 $1 \le e \le 200, a_i = 1, b_i = 1$。
另有 5 分满足 $1 \le e, a_i, b_i \le 2$。
另有 12 分满足 $N \le 200, 1 \le e, a_i, b_i \le 200$。
输出格式
输出一个整数，表示在出口隧道永远不会开启的情况下，可以分配到各个趣味房间的朋友的最大总数。