008 - 矢印
時間制限 1 秒 / メモリ制限 256 MB / 得点 11 / x 1 /
問題文
$L$個のマスが左右に一列に並んでいます。いくつかのマスの上に駒が置いてあります。駒には左向きか右向きの矢印が書いてあります。なお、一つのマスに二つ以上の駒を置くことはできません。
どのマスにいる駒も、駒が置かれていないマスに動かすことができます。ただし、一度に動けるのは隣のマスまでで、一度に動かせるのは一つの駒だけです。駒は、矢印の向きにかかわらず、左にも右にも動かすことができます。ただし、駒を矢印の方向に一回動かすと点数が1点もらえますが、矢印とは逆方向に一回動かすと1点減点されてしまいます。なお、どのような状況から始めたとしても、得られる点数には必ず最大値があることがわかっています。
マスの個数と駒の状況が与えられたとき、得られる最大の点数を計算するプログラムを作成せよ。ただし、マスには列の左端から順番に1から$L$までの番号が割り当てられているものとする。
入力
入力は以下の形式で与えられる。
$N$ $L$ $p_1$ $d_1$ $p_2$ $d_2$ : $p_N$ $d_N$
1行目に駒の数$N$ ($1 \leq N \leq 10^5$)とマスの数$L$ ($N \leq L \leq 10^9$)が与えられる。続く$N$行に駒が置かれたマスの番号$p_i$ ($1 \leq p_i \leq L$)と駒に書かれた矢印の向き$d_i$ (0または1)が与えられる。ただし、$d_i$が0のときは矢印が左向き、1のときは右向きを表す。同じマスの番号は与えられない($i \ne j$について、$p_i \ne p_j$)。
出力
得られる最大の点数を1行に出力する。
入出力例
入力例1
2 10 3 0 6 1
出力例1
6
入力例2
2 8 2 1 8 0
出力例2
5
入力例3
2 8 1 0 8 1
出力例3
0