← 返回题目列表

AtCoder · arc177_f

F. 两家航空公司

中文机器翻译题面 查看原题

分数: 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 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,和 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. 居民 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