Score: $1000$ points

问题陈述

AtCoder共和国由$L+1$个东西向排列的岛屿组成，从西向东编号为$0$到$L$。这些岛屿通过空中航线相连，对于每个$1 \leq i \leq L$，岛屿$i-1$和$i$之间有一条双向空中航线，如图中所示。每条航线由A公司或J公司拥有，岛屿$i-1$和$i$之间的航线由$S_i$公司拥有。

这个国家有$N$名居民，编号为$1$到$N$。居民$i$目前位于岛屿$X_i$。

每位居民都有一张公司的优惠券。具体来说，居民$i$有一张$C_i$公司的优惠券。凭借优惠券，居民可以无限次免费乘坐该公司的航线，但乘坐另一家公司的航线每次需要支付1枚硬币。

现在，岛屿$0$上有一个宝箱。居民们希望合作将其运送到首都，首都位于岛屿$L$。确定实现此目标所需的最少总硬币数。

居民们可以相互传递宝箱，但不能传递他们的优惠券。

以上为大语言模型 kimi 翻译，仅供参考。

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_1$$S_2$$\cdots$$S_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