题目内容

一条输油干线可以看成数轴上的闭区间 $[0,S]$。沿线已经安装了若干泵站。

现有 $n$ 座泵站。第 $i$ 座位于坐标 $p_i$，作用半径为 $w_i$，因此它能覆盖与 $p_i$ 距离不超过 $w_i$ 的所有位置。

还可以再安装若干座规格相同的新泵站。每座新泵站的作用半径都是 $R$，安装位置可以任选。

已有泵站与新泵站合在一起后，必须覆盖整个区间 $[0,S]$。请计算最少还需要安装多少座新泵站。

保证任意两座已有泵站的位置互不相同。

约束：干线长度不超过 10^9，已有泵站数量不超过 10^5，新泵站作用半径以及已有泵站作用半径均不超过 10^9。

输入描述

第一行包含三个整数 $S$、$n$ 和 $R$，依次表示干线长度、已有泵站数量和新泵站的作用半径。保证 $1 \le S \le 10^9$，$1 \le n \le 10^5$，$1 \le R \le 10^9$。 接下来 $n$ 行，第 $i$ 行包含两个整数 $p_i$ 和 $w_i$，表示第 $i$ 座已有泵站的位置与作用半径。保证 $1 \le p_i \le S$，$1 \le w_i \le 10^9$，且所有 $p_i$ 两两不同。

输出描述

输出一个整数，表示最少需要新装的泵站数量。

样例1

输入

10 1 5
5 5

输出

0

说明

唯一已有泵站位于 5、半径 5，覆盖整个 $[0,10]$。 无需新装，答案为 0。

样例2

输入

10 1 1
1 1

输出

4

说明

已有泵站覆盖 $[0,2]$。新泵站每座最多覆盖长度 $2R=2$。 剩余 $[2,10]$ 长度为 8，需要 $\lceil 8/2 \rceil=4$ 座新泵站。

样例3

输入

10 1 5
6 6

输出

0

说明

按题意模拟计算得到。