← 返回题目列表

AtCoder · arc041_c

C. 兔子跳

中文机器翻译题面 查看原题

問題文

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

兔子不会跳。