AT_tupc2022_b.Snowy Aobayama

あおばさん是仙台市一所大学的学生。
あおばさん每天都会根据路面积雪量来决定去大学的通学方式。
积雪量会因降雪和融雪而变化。

每天的流程如下：

• 首先发生降雪，积雪量会增加当天的降雪量。
• 接着发生融雪。如果此时的积雪量大于等于 $1\,\mathrm{cm}$，积雪量减少 $1\,\mathrm{cm}$。
• 最后，あおばさん根据此时的积雪量决定通学方式。如果积雪量大于等于 $K\,\mathrm{cm}$，则乘地铁；小于 $K\,\mathrm{cm}$ 则步行。

仙台市 $N$ 天内的降雪情况通过两个长度为 $M$ 的正整数列 $a_1<a_2<\dots<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$

请输出答案的整数。

样例解释 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$ 天。

样例解释 2

有时积雪量可能无法用 32 位整数表示。

数据范围

• $2 \leq N \leq 10^{12}$
• $1\leq M\leq 10^5$
• $1\leq K\leq 10^9$
• $1 \leq a_1<a_2<\dots<a_M \leq N$
• $1\leq b_i\le 10^9\ (i=1, 2, \dots, M)$
• 输入均为整数。

由 ChatGPT 5 翻译