F - Hands on Ring (Hard) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

注：この問題は B 問題とほぼ同じ設定です。本文中で太字で示されている部分および制約のみが異なります。

あなたはあるリングを両手で握っています。 このリングは N\ (N\geq 3) 個のパーツ 1,2,\dots,N によって構成されており、パーツ i とパーツ i+1 (1\leq i\leq N-1)、およびパーツ 1 とパーツ N がそれぞれ隣接しています。

最初、左手はパーツ 1 を、右手はパーツ 2 を握っています。 あなたは、1 回の 操作 で以下のことを行えます。

  • 片方の手を、今握っているパーツに隣接するいずれかのパーツに移動する。ただし、移動先にもう一方の手がない場合に限る。

以下の図は、初期状態およびそこから行える操作と行えない操作の例を示したもので、リングの各パーツに書き込まれた数はそのパーツの番号を、L と書かれた丸は左手を、R と書かれた丸は右手を示しています。

あなたは今から与えられる Q 個の指示に順番に従う必要があります。 i\ (1\leq i\leq Q) 個目の指示は文字 H_i および整数 T_i によって表され、その意味は以下の通りです：

  • 操作を何回か（0 回でもよい）行うことで、H_i が L ならば左手、R ならば右手が、パーツ T_i を握っている状態にする。 このとき、H_i によって指定された手ではない方の手を 動かしてもよい。

なお、本問題の設定および制約の下では、どのような指示も達成可能なことが証明できます。

すべての指示に従うために必要な操作回数の合計の最小値を求めてください。

制約

  • 3\leq N \leq 3000
  • 1\leq Q \leq 3000
  • H_i は L または R
  • 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 個の指示すべてに順番に従うことができます。

  1. 右手をパーツ 2\rightarrow 3\rightarrow 4 と移動させることで、1 番目の指示に従う。
  2. 左手をパーツ 1\rightarrow 6\rightarrow 5 と移動させることで、2 番目の指示に従う。
  3. 左手をパーツ 5\rightarrow 6 と移動させたのち、右手をパーツ 4\rightarrow 5 と移動させることで、3 番目の指示に従う。

このとき行う操作回数の合計は 2+2+1+1=6 であり、これが最小です。

入力例 2

100 2
L 1
R 2

出力例 2

0

操作を 1 度も行わずに指示に従うことができる場合もあります。

入力例 3

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

出力例 3

58

Score : 550 points

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