题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXV Olimpiada Informatyczna — III etap Dwa długie lizaki

Bajtazar 在巴托城经营一家糖果店，当地儿童最爱的是草莓香草棒棒糖。这些棒棒糖由不同长度的段组成，每段为单一口味，香草和草莓交替出现。

Bitek 和 Bajtok 来到店里，每人想买一支棒棒糖。Bajtazar 知道，若卖给他们的棒棒糖草莓和香草的含量不同，两个男孩定会争吵谁的更好。他们并不在意段的顺序或长度，只求总量相同。

店内恰有两支长序列棒棒糖，Bajtazar 想从第一支取一段卖给 Bitek，第二支取一段卖给 Bajtok。他允许在段内断裂，但卖出的片段需保持完整。

请帮助 Bajtazar 确定如何分割两支棒棒糖，使卖给男孩的片段尽可能长，且草莓与香草含量完全相同。

输入格式

输入依次描述两支长序列棒棒糖，格式相同。每支棒棒糖的描述如下：

第一行包含一个正整数 $m$，表示棒棒糖的段数。

接下来的 $m$ 行，每行包含一个字符 $t_i$ 和一个正整数 $a_i$，表示第 $i$ 段的类型：T 表示草莓，W 表示香草；$a_i$ 表示该段长度（单位：厘米）。

保证相邻两段类型不同。

输出格式

输出一行，包含一个整数，表示可从两支棒棒糖各取一段的最大长度，且两段草莓及香草含量相同。

3
T 5
W 7
T 4
3
W 6
T 6
W 6

13

提示

样例 1 解释

Bajtazar 可卖给男孩各含 $1$ 厘米草莓和 $2$ 厘米香草的片段。从第一支棒棒糖取整支（长度 $3$ 厘米，$2$ 厘米草莓，$1$ 厘米香草）。从第二支棒棒糖取前 $3$ 厘米（$1$ 厘米香草，$2$ 厘米草莓）。

附加样例

1. 第一支棒棒糖首段为香草，长度 $30$ 厘米，后续段 $1$ 厘米，$m=3$；第二支棒棒糖草莓、香草段交互，长度 $1,2$ 厘米，$m=5$，正确结果为 $8$。
2. 两支棒棒糖各 $m=10$，草莓、香草段交替出现，第一支段长 $1,2,3,\ldots,10$，第二支 $2,1,4,3,6,5,8,7,9,10$，正确结果为 $15$。
3. 两支棒棒糖各 $m=1000$，第一支自草莓始，第二支自香草始，所有段长 $1$ 厘米，正确结果为 $1000$。

令 $m_{\text{max}}$ 表示输入的最大段数，$n_{\text{max}}$ 表示棒棒糖的最大总长度。保证每个测试点满足 $n_{\text{max}} \leq 10^9, m_{\text{max}} \leq 10^5$。

详细子任务附加限制及分值如下表所示。