AT_arc177_f [ARC177F] Two Airlines

[problemUrl]: https://atcoder.jp/contests/arc177/tasks/arc177_f AtCoder 国は東西に並んでいる $ L+1 $ 個の島から成り、これらは西から順に $ 0 $ から $ L $ までの番号が付けられています。 島々は航空路線で結ばれており、下図のように各 $ 1\ \leq\ i\ \leq\ L $ について、島 $ i-1 $ と島 $ i $ を双方向に結ぶ航空路線があります。 ここで、各航空路線は A 社または J 社が所有しており、島 $ i-1 $ と島 $ i $ を結ぶ路線は $ S_i $ 社が所有しています。  また、AtCoder 国には $ N $ 人の住民がおり、それぞれ $ 1 $ から $ N $ までの番号が付けられています。 住民 $ i $ は現在島 $ X_i $ にいます。 さらに、各住民はいずれか一方の航空会社の**優待券**を持っており、具体的には、住民 $ i $ は $ C_i $ 社の優待券を持っています。 優待券を持っている会社の航空路線は**何度でも**無料で乗ることができますが、そうでない会社の航空路線に乗るには、$ 1 $ 回当たり $ 1 $ コインを支払う必要があります。 今、島 $ 0 $ に宝箱があります。これから AtCoder 国の住民で協力して、首都である島 $ L $ に宝箱を運びたいです。 最小で合計何コインで目的を達成できるかを求めてください。 なお、住民同士で宝箱の受け渡しをすることはできますが、優待券の受け渡しはできないものとします。

N/A

N/A

### 制約 - $ 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 $ は整数 ### Sample Explanation 1 以下のような手順を選択すると、合計 $ 2 $ コインで島 $ 4 $ に宝箱を運ぶことができます。 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 $ へ移動する。優待券の対象なのでコインを支払う必要はない。 !\[ \](https://img.atcoder.jp/arc177/362e9b56e8e71232a449db9eee2897d8.png)