← 返回题目列表

AtCoder · tupc2022_b

B. 雪青叶山

中文机器翻译题面 查看原题

配点 : 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