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 自动生成