分数: 550 点
问题陈述
注意:该问题与问题B的设置几乎相同,仅正文中粗体部分和约束条件有所不同。
您双手拿着一枚戒指。 该环由 N\ (N \geq 3) 零件编号 1,2,\dots,N,其中零件 i 和 i+1 (1 \leq i \leq N-1) 是相邻的,并且部分 1 和 N 也相邻。
最初,您的左手握住零件 1,并且你的右手拿着部分 2。 合而为一 操作,您可以执行以下操作:
- 将你的一只手移至当前所持部件的相邻部分。但是,只有当另一只手不在目标零件上时,您才能执行此操作。
下图显示了初始状态以及可以和不能从该状态进行的操作示例。戒指每个部分上写的数字代表零件编号,标记为 L 和 R 的圆圈分别代表您的左手和右手。

您需要遵循 Q 按顺序向您提供说明。 的 i-th (1 \leq i \leq Q) 指令由字符表示 H_i 和一个整数 T_i,含义如下:
- 执行一定数量的操作(可能为零),以便您的左手(如果 H_i is
L)或你的右手(如果 H_i isR) 正在持有部分 T_i。 在这里,你 可能 移动未指定的另一只手 H_i.
在本问题的设定和约束下,可以证明任何指令都是可以实现的。
找出遵循所有指令所需的最少操作总数。
约束
- 3\leq N \leq 3000
- 1\leq Q \leq 3000
- H_i is
LorR. - 1 \leq T_i \leq N
- N, Q,和 T_i 是整数。
输入
输入由标准输入按以下格式给出:
N Q H_1 T_1 H_2 T_2 \vdots H_Q T_Q
输出
打印遵循所有说明所需的最少操作总数。
样本输入 1
6 3 R 4 L 5 R 5
示例输出 1
6

通过执行以下操作,您可以遵循所有 Q 按顺序说明。
- 将右手作为一部分移动 2 \rightarrow 3 \rightarrow 4 遵循第一条指令。
- 将左手作为一部分移动 1 \rightarrow 6 \rightarrow 5 遵循第二条指令。
- 将左手作为一部分移动 5 \rightarrow 6,然后将右手作为一部分移动 4 \rightarrow 5 遵循第三条指令。
在这种情况下,操作总数为 2+2+1+1=6,这是最小值。
示例输入 2
100 2 L 1 R 2
示例输出 2
0
在某些情况下,您可以按照说明进行操作,而无需执行任何操作。
示例输入 3
30 8 R 23 R 26 R 29 L 20 R 29 R 19 L 7 L 16
示例输出 3
58