D - Hands on Ring (Easy) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

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

あなたはあるリングを両手で握っています。 このリングは 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 によって指定された手ではない方の手を 動かしてはならない。

なお、達成可能な指示しか与えられないことが保証されます。

詳細 この問題の設定の下では、各 i について、i 個目の指示に従う直前でのそれぞれの手の位置が一意に定まることが証明できます。 このとき、左手の位置をパーツ l_i、右手の位置をパーツ r_i とおくと、H_i= L ならば T_i\neq r_i が、H_i= R ならば T_i\neq l_i がそれぞれ保証されます。


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

制約

  • 3\leq N \leq 100
  • 1\leq Q \leq 100
  • 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 6

出力例 1

8

以下のように操作を行うことで、Q 個の指示すべてに順番に従うことができます。

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

このとき行う操作回数の合計は 2+2+4=8 であり、これが最小です。 （3 番目の指示に従う際に右手をパーツ 4\rightarrow 5\rightarrow 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

92

Score : 250 points

Problem Statement

Note: This problem has almost the same setting as Problem F. 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 must not move the other hand not specified by H_i.

It is guaranteed that only achievable instructions are given.

Details Under the settings of this problem, it can be proved that the positions of both hands are uniquely determined just before following the i-th instruction for each i. At that time, if we denote the positions of the left and right hands as parts l_i and r_i, respectively, it is guaranteed that T_i \neq r_i when H_i is L, and T_i \neq l_i when H_i is R.


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

Constraints

  • 3 \leq N \leq 100
  • 1 \leq Q \leq 100
  • H_i is L or R.
  • 1 \leq T_i \leq N
  • N, Q, and T_i are integers.
  • Only achievable instructions are given (see the problem statement for details).

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 6

Sample Output 1

8

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 right hand as part 4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 6 to follow the third instruction.

In this case, the total number of operations is 2+2+4=8, which is the minimum. (Note that when following the third instruction, you cannot move your right hand as part 4 \rightarrow 5 \rightarrow 6.)

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

92