双手绕环(Hard)

题目描述

注意:本题与 B 题的设定几乎相同。仅正文和约束条件中加粗的部分不同。

你用双手拿着一个圆环。 这个圆环由 $N\ (N \ge 3)$ 个部件组成,编号为 $1,2,\dots,N$,其中部件 $i$ 和部件 $i+1$($1 \le i \le N-1$)相邻,部件 $1$ 和部件 $N$ 也相邻。

初始时,你的左手拿着部件 $1$,右手拿着部件 $2$。 在一次操作中,你可以执行以下操作:

将一只手移动到它当前所拿部件的相邻部件。但是,只有当另一只手不在目标部件上时,才能执行该操作。

下图展示了初始状态以及此后可以进行和不能进行的操作示例。环上各部件上的数字代表部件编号,标有 L 和 R 的圆分别代表你的左手和右手。

你需要按顺序遵循 $Q$ 条指令。 第 $i$ 条($1 \le i \le Q$)指令由字符 $H_i$ 和整数 $T_i$ 表示,含义如下:

执行若干次操作(可以为 0 次),使得左手(如果 $H_i$ 为 L)或右手(如果 $H_i$ 为 R)拿着部件 $T_i$。 这里,你可以移动未被 $H_i$ 指定的另一只手。

在本问题的设定和约束下,可以证明任何指令都是可执行的。

求遵循所有指令所需的最少操作总次数。

输入格式

输入按以下格式从标准输入给出:

$N$ $Q$
$H_1$ $T_1$
$H_2$ $T_2$
$\vdots$
$H_Q$ $T_Q$

输出格式

输出遵循所有指令所需的最少操作总次数。

样例

6 3
R 4
L 5
R 5

6

按如下方式操作,可以按顺序遵循所有 $Q$ 条指令。

将右手从部件 $2 \rightarrow 3 \rightarrow 4$ 移动,以遵循第一条指令。

将左手从部件 $1 \rightarrow 6 \rightarrow 5$ 移动,以遵循第二条指令。

将左手从部件 $5 \rightarrow 6$ 移动,然后将右手从部件 $4 \rightarrow 5$ 移动,以遵循第三条指令。

此时,操作总次数为 $2+2+1+1=6$,这是最小值。

100 2
L 1
R 2

0

存在不需要执行任何操作就能遵循所有指令的情况。

30 8
R 23
R 26
R 29
L 20
R 29
R 19
L 7
L 16

58

数据范围

• $3 \le N \le 3000$
• $1 \le Q \le 3000$
• $H_i$ 是 L 或 R
• $1 \le T_i \le N$
• $N$, $Q$, $T_i$ 是整数