問題文
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
兔子不会跳。