题目描述

Vasya 最近在本地一家商店找了一份收银员的工作。他一天的工作时长为 $L$ 分钟。Vasya 已经记住了 $n$ 位常客，第 $i$ 位常客会在一天开始后的 $t_{i}$ 分钟到达，且为其服务需要 $l_{i}$ 分钟。保证在 Vasya 为某位顾客服务期间，不会有其他顾客到达。

Vasya 有点懒惰，所以他喜欢每次抽烟休息 $a$ 分钟。这些休息可以连续进行，但 Vasya 必须在所有需要为常客服务的时间段内在岗，否则其中一位顾客可能会告发他。请问 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$。

输出格式

输出一个整数，表示 Vasya 最多可以休息的次数。

说明/提示

在第一个样例中，Vasya 可以在第 $2$、$5$ 和 $8$ 分钟后各休息 $3$ 次。

在第二个样例中，Vasya 可以在第 $0$ 和 $2$ 分钟后各休息 $2$ 次。

在第三个样例中，Vasya 无法休息。

由 ChatGPT 4.1 翻译

样例

2 11 3
0 1
1 1

3

0 5 2

2

1 3 2
1 2

0