P12769 [POI 2018 R3] 两根长棒 Two long candy sticks

翻译来自于 [LibreOJ](https://loj.ac/p/5077)。

**题目译自 [XXV Olimpiada Informatyczna — III etap](https://sio2.mimuw.edu.pl/c/oi25-3/dashboard/) [Dwa długie lizaki](https://szkopul.edu.pl/problemset/problem/Kmofhbw9cTx06gSZg-C5MiBU/statement/)** Bajtazar 在巴托城经营一家糖果店，当地儿童最爱的是草莓香草棒棒糖。这些棒棒糖由不同长度的段组成，每段为单一口味，香草和草莓交替出现。 Bitek 和 Bajtok 来到店里，每人想买一支棒棒糖。Bajtazar 知道，若卖给他们的棒棒糖草莓和香草的含量不同，两个男孩定会争吵谁的更好。他们并不在意段的顺序或长度，只求总量相同。 店内恰有两支长序列棒棒糖，Bajtazar 想从第一支取一段卖给 Bitek，第二支取一段卖给 Bajtok。他允许在段内断裂，但卖出的片段需保持完整。 请帮助 Bajtazar 确定如何分割两支棒棒糖，使卖给男孩的片段尽可能长，且草莓与香草含量完全相同。

输入依次描述两支长序列棒棒糖，格式相同。每支棒棒糖的描述如下： 第一行包含一个正整数 $m$，表示棒棒糖的段数。 接下来的 $m$ 行，每行包含一个字符 $t_i$ 和一个正整数 $a_i$，表示第 $i$ 段的类型：T 表示草莓，W 表示香草；$a_i$ 表示该段长度（单位：厘米）。 保证相邻两段类型不同。

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

**样例 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$。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n_{\text{max}} \leq 15$ | $15$ | | $2$ | $n_{\text{max}} \leq 3000$ | $12$ | | $3$ | $n_{\text{max}} \leq 500000, m_{\text{max}} \leq 15$ | $15$ | | $4$ | $m_{\text{max}} \leq 150$ | $8$ | | $5$ | $n_{\text{max}} \leq 500000, m_{\text{max}} \leq 300$ | $15$ | | $6$ | $m_{\text{max}} \leq 300$ | $15$ | | $7$ | $n_{\text{max}} \leq 5000000$ | $10$ | | $8$ | 无附加限制 | $30$ |