Problem:

矢印

　

  $L$個のマスが左右に一列に並んでいます。いくつかのマスの上に駒が置いてあります。駒には左向きか右向きの矢印が書いてあります。なお、一つのマスに二つ以上の駒を置くことはできません。

  どのマスにいる駒も、駒が置かれていないマスに動かすことができます。ただし、一度に動けるのは隣のマスまでで、一度に動かせるのは一つの駒だけです。駒は、矢印の向きにかかわらず、左にも右にも動かすことができます。ただし、駒を矢印の方向に一回動かすと点数が１点もらえますが、矢印とは逆方向に一回動かすと１点減点されてしまいます。なお、どのような状況から始めたとしても、得られる点数には必ず最大値があることがわかっています。

  マスの個数と駒の状況が与えられたとき、得られる最大の点数を計算するプログラムを作成せよ。ただし、マスには列の左端から順番に1から$L$までの番号が割り当てられているものとする。

入力

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

$N$ $L$
$p_1$ $d_1$
$p_2$ $d_2$
:
$p_N$ $d_N$

１行目に駒の数$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$）。

出力

  得られる最大の点数を１行に出力する。

入出力例

入力例１

2 10
3 0
6 1

出力例１

6

入力例２

2 8
2 1
8 0

出力例２

5

入力例３

2 8
1 0
8 1

出力例３

0



Sample input:
2 10
3 0
6 1


Sample output:
6

Submission status: Accepted

Solution code:
# AOJ Volume4 0411
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0411

N, L = list(map(int, input().split()))
c = []
for _ in range(0, N):
    p, d = list(map(int, input().split()))
    c += [(p, d)]
c.sort()
masu = [p for p, d in c]
dir  = [d for p, d in c]

result = 0

score = 0
for j in range(0, N):
    if dir[j] == 0:
        score += masu[j] - j - 1
    elif dir[j] == 1:
        score -= masu[j] - j - 1
    masu[j] = j + 1
result = score

for i in range(N - 1, -1, -1):
    if dir[i] == 1:
        score += L - (N - i) - masu[i] + 1
    elif dir[i] == 0:
        score -= L - (N - i) - masu[i] + 1
    masu[i] = L - (N - i) + 1
    
    result = max(result, score)
print(result)