F - Two Airlines Editorial /

Time Limit: 5 sec / Memory Limit: 2048 MB

配点 : 1000 点

問題文

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 に宝箱を運びたいです。 最小で合計何コインで目的を達成できるかを求めてください。

なお、住民同士で宝箱の受け渡しをすることはできますが、優待券の受け渡しはできないものとします。

制約

  • 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 は整数

入力

入力は以下の形式で標準入力から与えられます。 

L N
S_1S_2\cdotsS_L
X_1 C_1
X_2 C_2
 \vdots
X_N C_N

入力の 2 行目は長さ L の文字列として与えられることに注意してください。

出力

答えを出力してください。

入力例 1

4 3
AAJJ
3 A
1 J
1 J

出力例 1

2

以下のような手順を選択すると、合計 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 へ移動する。優待券の対象なのでコインを支払う必要はない。

入力例 2

8 3
JJAAJJAJ
2 A
6 A
8 J

出力例 2

6

入力例 3

8 6
JJAAJJAJ
2 A
6 A
8 J
8 J
8 J
8 J

出力例 3

4

Score: 1000 points

Problem Statement

The Republic of AtCoder consists of L+1 islands aligned east-west, numbered 0 to L from west to east. The islands are connected by air routes, where for each 1 \leq i \leq L, there is a bidirectional air route between islands i-1 and i, as shown in the figure below. Each air route is owned by company A or company J, and the route between islands i-1 and i is owned by company S_i.

The nation has N residents, numbered 1 to N. Resident i is currently on island X_i.

Each resident has a coupon of one of the companies. Specifically, resident i has a coupon of company C_i. With a coupon, a resident can take that company's routes for free any number of times, but taking a route of the other company costs 1 coin per trip.

Now, there is a treasure chest on island 0. The residents want to cooperate to carry it to the capital, which is on island L. Determine the minimum total number of coins required to achieve this goal.

The residents can pass the treasure chest to each other, but not their coupons.

Constraints

  • 1 \leq L \leq 6 \times 10^4
  • 1 \leq N \leq 6 \times 10^4
  • S_i \ (1 \leq i \leq L) is A or J.
  • 0 \leq X_i \leq L \ (1 \leq i \leq N)
  • C_i \ (1 \leq i \leq N) is A or J.
  • L, N, and X_i are integers.

Input

The input is given from Standard Input in the following format:

L N
S_1S_2\cdotsS_L
X_1 C_1
X_2 C_2
 \vdots
X_N C_N

Note that the second line is given as a string of length L.

Output

Print the answer.

Sample Input 1

4 3
AAJJ
3 A
1 J
1 J

Sample Output 1

2

The following procedure carries the treasure chest to island 4 for a total of 2 coins.

  1. Resident 1 moves from island 3 to island 2. The route is not covered by the coupon, so 1 coin is paid.
  2. Resident 1 moves from island 2 to island 1. The route is covered by the coupon, so no coin is needed.
  3. Resident 1 moves from island 1 to island 0. The route is covered by the coupon, so no coin is needed.
  4. Resident 1 picks up the treasure chest.
  5. Resident 1, carrying the treasure chest, moves from island 0 to island 1. The route is covered by the coupon, so no coin is needed.
  6. Resident 1 passes the treasure chest to resident 2.
  7. Resident 2, carrying the treasure chest, moves from island 1 to island 2. The route is not covered by the coupon, so 1 coin is paid.
  8. Resident 2, carrying the treasure chest, moves from island 2 to island 3. The route is covered by the coupon, so no coin is needed.
  9. Resident 2, carrying the treasure chest, moves from island 3 to island 4. The route is covered by the coupon, so no coin is needed.

Sample Input 2

8 3
JJAAJJAJ
2 A
6 A
8 J

Sample Output 2

6

Sample Input 3

8 6
JJAAJJAJ
2 A
6 A
8 J
8 J
8 J
8 J

Sample Output 3

4