#P6713. [CCO2018] Geese vs. Hawks

[CCO2018] Geese vs. Hawks

题目背景

本题题面来自 LOJ

题目描述

Troy 和 JP 是冰球迷。这个赛季每个冰球队会进行 NN 场比赛。每场比赛在两个队之间进行,得分更高者胜。并且不会出现平局的情况。

Troy 最喜欢的队伍是滑铁卢野鹅队,他记录了这个队每场比赛的结果。比赛结果记作一个字符串 SS。如果野鹅队赢下了第 ii 场比赛,则 Si=WS_i=\texttt{W},否则 Si=LS_i=\texttt{L}。他同时记下了在第 ii 场比赛,他们获得了 AiA_i 分。

JP 最喜欢的队伍是劳里埃金鹰队,他也记录了这个队每场比赛的结果。比赛结果记作一个字符串 TT。如果金鹰队赢下了第 jj 场比赛,则 Tj=WT_j=\texttt{W},否则 Tj=LT_j=\texttt{L}。他同时记下了在第 jj 场比赛,他们获得了 BjB_j 分。

Troy 和 JP 均按顺序记录了他们喜欢的队伍每场比赛的结果和分数。

一次同城德比是指一场滑铁卢野鹅对劳里埃金鹰的比赛(因为两队主场均在滑铁卢)。因为 Tory 和 JP 都没有记录他们最喜欢的球队在比赛中的对手,所以他们不能确定有没有同城德比,也确定不了哪些场比赛是同城德比。他们想知道,根据他们记录的信息推算,在所有同城德比中,两队取得分数总和的最大值是多少。

输入格式

第一行包含一个整数 NN

第二行包含一个长为 NN 的字符串 SS,保证字符串 SS 中只包含 W\texttt{W}L\texttt{L}

第三行包含 NN 个整数 A1,,ANA_1,\ldots ,A_N

第四行包含一个长为 NN 的字符串 TT,保证字符串 TT 中只包含 W\texttt{W}L\texttt{L}

第五行包含 NN 个整数 B1,,BNB_1,\ldots ,B_N

输出格式

输出一行一个整数,表示在所有同城德比中,两队取得分数总和的最大值。

1
W
2
W
3
0
4
WLLW
1 2 3 4
LWWL
6 5 3 2
14

提示

样例解释

样例 1 解释

因为两队都赢了比赛,因此不会出现同城德比。

样例 2 解释

两队各自进行的第四场比赛可能是同城德比,野鹅队得 44 分,金鹰队得 22 分。野鹅队进行的第三场比赛和金鹰队进行的第二场比赛可能是同城德比,金鹰队得 55 分,野鹅队得 33 分。两队得分总和为 4+2+5+3=144 + 2 + 5 + 3 = 14,并且是得分总和最大的情况。

注意野鹅队的第一场比赛赢了,并且得了 11 分,这场比赛不可能是对金鹰的,因为金鹰队没有得 00 分的比赛。同时,金鹰队的第一场比赛也不可能是同城德比,因为金鹰队第一场比赛输了,并且得了 66 分,野鹅队没有打出过获得至少 77 分的比赛。

数据范围及限制

对于 100%100\% 的数据,保证 1N1031\le N\le 10^31Ai,Bi1061\le A_i,B_i\le 10^6Si,Ti{S_i,T_i\in\{WL}\}

  • Subtask 1(4040 分):保证 N10N\le 10
  • Subtask 2(6060 分):无特殊限制。

说明

本题译自 Canadian Computing Olympiad 2020 Day 1 T1 Geese vs. Hawks。