AT_arc177_f [ARC177F] Two Airlines

在 AtCoder 国，有一排共 $L+1$ 个岛屿，从西至东依次编号为 $0$ 到 $L$。这些岛通过航空线路连接，每条连接线双向可通。对于每个 $1 \leq i \leq L$，岛屿 $i-1$ 和岛屿 $i$ 由一条线路连接。每一条航空路线都由 A 公司或 J 公司运营，具体来说，连接岛屿 $i-1$ 和岛屿 $i$ 的线路属于 $S_i$ 公司。  这个国家有 $N$ 位居民，他们被编号为 $1$ 到 $N$。每位居民目前分别位于岛屿 $X_i$ 上。 每位居民都持有一张某个公司的优惠券。具体来说，居民 $i$ 拿着的是 $C_i$ 公司的优惠券。他们可以免费搭乘优惠券对应公司的航班任意次，而搭乘其他公司航班时，每次需要支付 $1$ 枚硬币。 我们的目标是把位于岛屿 $0$ 的宝藏运送到首都岛屿 $L$。为了实现这一目标，请计算最少需要支付多少枚硬币。 请注意，宝藏可以在居民之间转交，但优惠券不允许转让。

输入通过以下格式标准输入： > $L$ $N$ > > $S_1 S_2 \cdots S_L$ > > $X_1$ $C_1$ > > $X_2$ $C_2$ > > $\vdots$ > > $X_N$ $C_N$ 注意第 $2$ 行是一个长度为 $L$ 的字符串。

输出为一个整数表示所需的最少硬币数量。

### 条件限制 - $1 \leq L \leq 6 \times 10^4$ - $1 \leq N \leq 6 \times 10^4$ - $S_i\ (1 \leq i \leq L)$ 是 `A` 或 `J` - $0 \leq X_i \leq L\ (1 \leq i \leq N)$ - $C_i\ (1 \leq i \leq N)$ 是 `A` 或 `J` - $L, N, X_i$ 是整数 ### 示例解释 下面的操作可使宝藏被运送到岛屿 $4$，总共只需花费 $2$ 枚硬币： 1. 居民 $1$ 从岛 $3$ 移到岛 $2$。因为不是优惠券适用的公司航班，所以花费 $1$ 枚硬币。 2. 居民 $1$ 从岛 $2$ 到岛 $1$，在这个过程中无需支付，因为这是他拥有优惠券的公司路线。 3. 居民 $1$ 从岛 $1$ 到岛 $0$，免费，因为使用的是优惠券航班。 4. 居民 $1$ 拿起宝藏。 5. 居民 $1$ 带着宝藏，从岛 $0$ 移动到岛 $1$，依旧免费。 6. 居民 $1$ 把宝藏交给居民 $2$。 7. 居民 $2$ 带着宝藏，从岛 $1$ 到岛 $2$，这条航线不适用他的优惠券，花费 $1$ 枚硬币。 8. 居民 $2$ 继续从岛 $2$ 到岛 $3$，免费，因为使用了他公司的航班。 9. 最后，居民 $2$ 从岛 $3$ 到岛 $4$，依旧免费。  **本翻译由 AI 自动生成**