Score : $550$ points

问题陈述

注意：这个问题的设置几乎与问题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$个（$1 \leq i \leq Q$）指令由一个字符$H_i$和一个整数$T_i$表示，含义如下：

• 执行一些操作（可能是零），以便你的左手（如果$H_i$是L）或右手（如果$H_i$是R）拿着第$T_i$部分。在这里，你可以移动$H_i$未指定的另一只手。

在这个问题的设置和约束条件下，可以证明任何指令都是可实现的。

找出遵循所有指令所需的最小总操作数。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

Note: This problem has almost the same setting as Problem B. Only the parts in bold in the main text and constraints differ.

You are holding a ring with both hands. This ring consists of $N\ (N \geq 3)$ parts numbered $1,2,\dots,N$, where parts $i$ and $i+1$ ($1 \leq i \leq N-1$) are adjacent, and parts $1$ and $N$ are also adjacent.

Initially, your left hand is holding part $1$, and your right hand is holding part $2$. In one operation, you can do the following:

• Move one of your hands to an adjacent part of the part it is currently holding. However, you can do this only if the other hand is not on the destination part.

The following figure shows the initial state and examples of operations that can and cannot be made from there. The number written on each part of the ring represents the part number, and the circles labeled L and R represent your left and right hands, respectively.

You need to follow $Q$ instructions given to you in order. The $i$-th ($1 \leq i \leq Q$) instruction is represented by a character $H_i$ and an integer $T_i$, meaning the following:

• Perform some number of operations (possibly zero) so that your left hand (if $H_i$ is L) or your right hand (if $H_i$ is R) is holding part $T_i$. Here, you may move the other hand not specified by $H_i$.

Under the settings and constraints of this problem, it can be proved that any instructions are achievable.

Find the minimum total number of operations required to follow all the instructions.

Constraints

• $3\leq N \leq 3000$
• $1\leq Q \leq 3000$
• $H_i$ is L or R.
• $1 \leq T_i \leq N$
• $N$, $Q$, and $T_i$ are integers.

Input

The Input is given from Standard Input in the following format:

$N$ $Q$

$H_1$ $T_1$

$H_2$ $T_2$

$\vdots$

$H_Q$ $T_Q$

Output

Print the minimum total number of operations required to follow all the instructions.

Sample Input 1

6 3
R 4
L 5
R 5

Sample Output 1

6

By performing the following operations, you can follow all $Q$ instructions in order.

1. Move your right hand as part $2 \rightarrow 3 \rightarrow 4$ to follow the first instruction.
2. Move your left hand as part $1 \rightarrow 6 \rightarrow 5$ to follow the second instruction.
3. Move your left hand as part $5 \rightarrow 6$, then move your right hand as part $4 \rightarrow 5$ to follow the third instruction.

In this case, the total number of operations is $2+2+1+1=6$, which is the minimum.

Sample Input 2

100 2
L 1
R 2

Sample Output 2

0

There are cases where you can follow the instructions without performing any operations.

Sample Input 3

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

Sample Output 3

58