C - ウサギ跳び Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

L 個のマスが横一列に並んでいる。 マスの上には N 匹のウサギがいる。 i (1≦i≦N) 番目のウサギは、左から x_i 番目のマスにいる。 ただし、1≦x_1<x_2<..<x_N≦L を満たす。 また、ウサギはそれぞれ左向きまたは右向きである。

それぞれのウサギは、自分の 1 つ前にマスが存在し、そこに他のウサギがいなければ、ジャンプして自分の 1 つ前のマスへ移動できる。

ウサギがジャンプする順番を自由に選べるとき、ジャンプの総回数の最大値を求めよ。

入力

入力は以下の形式で標準入力から与えられる。

N L
x_1 d_1
x_2 d_2
:
x_N d_N
  • 1 行目には、ウサギの匹数 N (1≦N≦10^5) とマスの個数 L (N≦L≦10^9) が空白区切りで与えられる。
  • 2 行目からの N 行には、ウサギの情報が与えられる。このうち i 行目には、i 番目のウサギの位置 x_i と向き d_i が空白区切りで与えられる。ただし、d_i は L（左向き）または R（右向き）である。
  • 1≦x_1<x_2<..<x_N≦L を満たす。

出力

ウサギがジャンプする順番を自由に選べるとき、ジャンプの総回数の最大値を 1 行に出力せよ。 出力の末尾に改行を入れること。

入力例1

1 5
1 R

出力例1

4

図のようにジャンプすればよい。

入力例2

4 5
1 R
3 L
4 L
5 L

出力例2

3

図のようにジャンプすればよい。

入力例3

4 10
1 L
5 R
6 L
10 R

出力例3

0

どのウサギもジャンプできない。