← 返回题目列表

Codeforces · 1059/A

A. 收银员

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

Vasya 最近在当地一家商店找到了一份收银员的工作。他一天的工作时间长达 $$$L$$$ 分钟。 Vasya 已经记住了 $$$n$$$ 个常客,其中第 $$$i$$$ 个是在一天开始后 $$$t_{i}$$$ 分钟之后,他的服务消耗了 $$$l_{i}$$$ 分钟。保证在 Vasya 为另一位顾客提供服务时不会有任何顾客到达。

Vasya 有点懒,所以他喜欢每次吸烟 $$$a$$$ 分钟。这些休息时间可能会接连不断,但瓦夏在必须为常客提供服务的所有时间段内都必须在场,否则其中一个可能会提醒他的老板。 Vasya 一天最多可以休息多少次?

输入

第一行包含三个整数 $$$n$$$、$$$L$$$ 和 $$$a$$$ ($$$0 \le n \le 10^{5}$$$、$$$1 \le L \le 10^{9}$$$、$$$1 \le a \le L$$$)。

接下来的 $$$n$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$t_{i}$$$ 和 $$$l_{i}$$$ ($$$0 \le t_{i} \le L - 1$$$, $$$1 \le l_{i} \le L$$$)。保证 $$$t_{i} + l_{i} \le t_{i + 1}$$$ 和 $$$t_{n} + l_{n} \le L$$$。

输出

输出一个整数——最大中断数。

示例

输入 #1

2 11 3
0 1
1 1

输出 #1

3

输入 #2

0 5 2

输出 #2

2

输入 #3

1 3 2
1 2

输出 #3

0

注意

在第一个示例中,Vasya 可以在一天开始后的 $$$2$$$、$$$5$$$ 和 $$$8$$$ 分钟后开始休息 $$$3$$$。

在第二个示例中,Vasya 可以在 $$$0$$$ 后和一天开始后 $$$2$$$ 分钟后开始休息 $$$2$$$。

在第三个样本中,Vasya 无法休息。