配点 : 200 点
問題文
A阿姨是仙台市一所大学的大学生。
阿姨每天根据路上积雪的多少来决定如何去大学。
降雪量根据降雪和融雪而变化。
每天的流程如下。
- 首先,下雪了。降雪量随着当天的降雪量而增加。
- 接下来是融雪。当时的降雪量为 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)
- 输入全部为整数
入力
输入是按以下格式从标准输入给出的。
N M K a_1 b_1 a_2 b_2 \vdots a_M b_M
出力
将答案打印为整数。
入力例 1
8 3 2 2 4 7 1 8 3
出力例 1
3
每日降雪量变化如下。
| 日 | 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
5 5 1 1 1000000000 2 1000000000 3 1000000000 4 1000000000 5 1000000000
出力例 2
5
降雪量可能不适合 32 位整数。
入力例 3
28 9 2 4 2 5 2 10 5 15 5 17 1 18 2 20 2 21 1 22 1
出力例 3
14