問題文

あおばさんは仙台市の大学に通う大学生です。
あおばさんは、毎日路面の積雪量によって大学への通学手段を決定します。
積雪量は降雪や融雪によって変化します。

各日の流れは以下の通りです。

• まず降雪が起こる。その日の降雪量の分だけ積雪量が増加する。
• 次に融雪が起こる。その時点での積雪量が 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も参考にしてください。

制約

• 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)
• 入力はすべて整数

入力例 1

8 3 2
2 4
7 1
8 3

出力例 1

3

各日の積雪量の変化は以下の通りです。

よって、地下鉄を利用したのは2, 3, 8日目の3日間です。

入力例 2

5 5 1
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000

出力例 2

5

積雪量が32bit整数に収まらない場合があります。

入力例 3

28 9 2
4 2
5 2
10 5
15 5
17 1
18 2
20 2
21 1
22 1

出力例 3

14