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$。为了实现这一目标，请计算最少需要支付多少枚硬币。需要注意的是，宝箱可以在居民之间转交，但优惠券不允许转让。

无

无

### 条件限制 - $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 自动生成**