008 - 矢印

時間制限 1 秒 / メモリ制限 256 MB / 得点 11 / x 1 /


TLE
1sec
MLE
256MB
得点
11

問題文

$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