{"problem":{"name":"Two Airlines","description":{"content":"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 bidire","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc177_f"},"statements":[{"statement_type":"Markdown","content":"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$.\n![image](https://img.atcoder.jp/arc177/dacd06e6239af911b67dfbb502b35bcd.png)\nThe nation has $N$ residents, numbered $1$ to $N$. Resident $i$ is currently on island $X_i$.\nEach 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.\nNow, 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.\nThe residents can pass the treasure chest to each other, but not their coupons.\n\n## Constraints\n\n*   $1 \\leq L \\leq 6 \\times 10^4$\n*   $1 \\leq N \\leq 6 \\times 10^4$\n*   $S_i \\ (1 \\leq i \\leq L)$ is `A` or `J`.\n*   $0 \\leq X_i \\leq L \\ (1 \\leq i \\leq N)$\n*   $C_i \\ (1 \\leq i \\leq N)$ is `A` or `J`.\n*   $L$, $N$, and $X_i$ are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$L$ $N$\n$S_1$$S_2$$\\cdots$$S_L$\n$X_1$ $C_1$\n$X_2$ $C_2$\n $\\vdots$\n$X_N$ $C_N$\n\nNote that the second line is given as a string of length $L$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc177_f","tags":[],"sample_group":[["4 3\nAAJJ\n3 A\n1 J\n1 J","2\n\nThe following procedure carries the treasure chest to island $4$ for a total of $2$ coins.\n\n1.  Resident $1$ moves from island $3$ to island $2$. The route is not covered by the coupon, so $1$ coin is paid.\n2.  Resident $1$ moves from island $2$ to island $1$. The route is covered by the coupon, so no coin is needed.\n3.  Resident $1$ moves from island $1$ to island $0$. The route is covered by the coupon, so no coin is needed.\n4.  Resident $1$ picks up the treasure chest.\n5.  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.\n6.  Resident $1$ passes the treasure chest to resident $2$.\n7.  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.\n8.  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.\n9.  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.\n\n![image](https://img.atcoder.jp/arc177/9545d9fbdd7defc8d56f84380765a3d7.png)"],["8 3\nJJAAJJAJ\n2 A\n6 A\n8 J","6"],["8 6\nJJAAJJAJ\n2 A\n6 A\n8 J\n8 J\n8 J\n8 J","4"]],"created_at":"2026-03-03 11:01:14"}}