AT_tupc2022_b Snowy Aobayama

あおばさんは仙台市の大学に通う大学生です。 あおばさんは、毎日路面の積雪量によって大学への通学手段を決定します。 積雪量は降雪や融雪によって変化します。 各日の流れは以下の通りです。 - まず降雪が起こる。その日の降雪量の分だけ積雪量が増加する。 - 次に融雪が起こる。その時点での積雪量が $ 1 $ $ [\mathrm{cm}] $ 以上である場合、積雪量が $ 1 $ $ [\mathrm{cm}] $ 減少する。 - 最後にあおばさんが通学手段を決定する。その時点の積雪量が $ K $ $ [\mathrm{cm}] $ 以上ならば地下鉄を使って、 $ K $ $ [\mathrm{cm}] $ 未満ならば徒歩で通学する。 仙台市の $ N $ 日間の降雪量の情報が長さ $ M $ の正整数列 $ a_1\lt a_2\lt \dots\lt a_M $ と $ b_1,b_2,\dots,b_M $ によって与えられます。 これは、 $ a_i $ 日目の降雪量が $ b_i $ $ [\mathrm{cm}] $ であったことを表します。それ以外の日の降雪量は $ 0 $ $ [\mathrm{cm}] $ でした。 この $ N $ 日間のうち、あおばさんが地下鉄を使ったのは延べ何日間ありますか。 ただし、 $ 1 $ 日目より前の積雪量は $ 0 $ $ [\mathrm{cm}] $ であったとします。 積雪量の変化の状況については入出力例1も参考にしてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ \vdots $ $ a_M $ $ b_M $

答えを整数で出力せよ。

### Sample Explanation 1 各日の積雪量の変化は以下の通りです。 日 $ 1 $ $ 2 $ $ 3 $ $ 4 $ $ 5 $ $ 6 $ $ 7 $ $ 8 $ 降雪量 $ 0 $ $ 4 $ $ 0 $ $ 0 $ $ 0 $ $ 0 $ $ 1 $ $ 3 $ 積雪変化 $ \pm0 $ $ +4 $ , $ -1 $ $ -1 $ $ -1 $ $ -1 $ $ \pm0 $ $ +1 $ , $ -1 $ $ +3 $ , $ -1 $ 積雪量 $ 0 $ $ 3 $ $ 2 $ $ 1 $ $ 0 $ $ 0 $ $ 0 $ $ 2 $ 通学手段 徒歩 地下鉄 地下鉄 徒歩 徒歩 徒歩 徒歩 地下鉄 よって、地下鉄を利用したのは $ 2, 3, 8 $ 日目の $ 3 $ 日間です。 ### Sample Explanation 2 積雪量が32bit整数に収まらない場合があります。 ### Constraints - $ 2 \leq N \leq 10^{12} $ - $ 1\leq M\leq 10^5 $ - $ 1\leq K\leq 10^9 $ - $ 1 \leq a_1\lt a_2\lt \dots\lt a_M \leq N $ - $ 1\leq b_i\le 10^9\ (i=1, 2, \dots, M) $ - 入力はすべて整数