分数: 1000 点
问题陈述
AtCoder 共和国包括 L+1 岛屿东西向排列,编号 0 to L 从西到东。 这些岛屿通过航线相连,每个岛屿 1 \leq i \leq L,岛屿之间有双向航线 i-1 和 i,如下图所示。 每条航线均属于A公司或J公司所有,岛屿之间的航线 i-1 和 i 归公司所有 S_i.

国家有 N 居民,编号 1 to N。 居民 i 目前在岛上 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) is
AorJ. - 0 \leq X_i \leq L \ (1 \leq i \leq N)
- C_i \ (1 \leq i \leq N) is
AorJ. - L, N,和 X_i 是整数。
输入
输入由标准输入按以下格式给出:
L N S_1S_2\cdotsS_L X_1 C_1 X_2 C_2 \vdots X_N C_N
请注意,第二行以长度为字符串的形式给出 L.
输出
打印答案。
示例输入 1
4 3 AAJJ 3 A 1 J 1 J
示例输出 1
2
以下程序将宝箱运到岛上 4 总共 2 硬币。
- 居民 1 从岛上搬出 3 去岛 2。该路线不在优惠券范围内,所以 1 硬币已支付。
- 居民 1 从岛上搬出 2 去岛 1。该路线已包含在优惠券内,因此无需硬币。
- 居民 1 从岛上搬出 1 去岛 0。该路线已包含在优惠券内,因此无需硬币。
- 居民 1 拿起宝箱。
- 居民 1,携带宝箱,从岛屿出发 0 去岛 1。该路线已包含在优惠券内,因此无需硬币。
- 居民 1 将宝箱传递给居民 2.
- 居民 2,携带宝箱,从岛屿出发 1 去岛 2。该路线不在优惠券范围内,所以 1 硬币已支付。
- 居民 2,携带宝箱,从岛屿出发 2 去岛 3。该路线已包含在优惠券内,因此无需硬币。
- 居民 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