题目描述

题目译自 XXX Olimpiada Informatyczna – I etap Wyprzedzanie

Bajtazar 开着他的新跑车去海边。他正在高速公路上行驶。作为一个合格的司机，他一直保持在右车道，但是在他前面的右车道上还有 $n$ 辆卡车需要超过。

我们按照离 Bajtazar 的车的距离从进到远的顺序 $1$ 到 $n$ 给卡车编号。第 $i$ 辆卡车的速度是 $v_{i}$，长度是 $d_{i}$，并且在初始时刻距离 Bajtazar 的车有 $x_{i}$ 的距离。为了简化，我们把车看作是没有边缘的矩形，它们的位置就是它们的前边。

如果由于速度差，第 $i$ 辆卡车的前面和它前面的卡车（编号为 $i+1$）的后面对齐了，那么第 $i$ 辆卡车就会减速到第 $i+1$ 辆卡车的速度（也就是说，卡车之间不会相互超车）。

Bajtazar 的速度是 $V$，他的车的速度比所有卡车都快，他的车的长度是 $D$。当他的车的前面和某辆卡车的后面对齐时，Bajtazar 立刻执行换道的动作，继续在左车道上行驶。只要有可能换回右车道，Bajtazar 就会执行这个动作（即使在同一时刻他又必须换回左车道）。

Bajtazar 想知道，在超过所有卡车的过程中，他会执行多少次从右车道换到左车道的动作。我们假设现在高速公路上没有其他的车辆。

输入格式

第一行包含四个整数 $n, D, W, M\ (1 \leq n \leq 100000,1 \leq D \leq 10^{9}, 1 \leq W, M \leq 1000)$，表示卡车的数量，Bajtazar 的汽车的长度和速度，速度的公式是 $V=\frac{W}{M}$。

接下来的 $n$ 行包含卡车的描述：第 $i$ 行包含四个整数 $x_{i}, d_{i}$, $w_{i}, m_{i}\ (1 \leq x_{i}, d_{i} \leq 10^{9}, 1 \leq w_{i}, m_{i} \leq 1000)$。卡车的速度是 $v_{i}=\frac{w_{i}}{m_{i}}$。

车辆之间不会重叠，也就是说对于 $1 \leq i<n$，有 $0 \leq x_{1}-d_{1}$ 且 $x_{i} \leq x_{i+1}-d_{i+1}$。

所有的长度和位置都用距离单位表示，速度用距离单位除以时间单位表示。

输出格式

输出一行一个整数，表示 Bajtazar 执行变换到左边车道的操作的次数。

3 1 1 1
3 2 1 4
6 3 1 2
10 2 1 4

2

Bajtazar 的汽车以速度 $1$ 行驶，而卡车以速度 $\frac{1}{4}, \frac{1}{2}, \frac{1}{4}$ 行驶。在时刻 $\frac{4}{3}$，Bajtazar 追上第一辆卡车并变换到左边车道，在时刻 $\frac{16}{3}$ 他又回到右边车道。在时刻 $6$，他第二次变换到左边车道。在时刻 $8$，第二辆卡车追上第三辆卡车并降低速度到 $\frac{1}{4}$。在时刻 $\frac{44}{3}$，Bajtazar 回到右边车道。

样例 2

见附加文件下 [wyp1.in](file:wyp1.in) 和 [wyp1.out](file:wyp1.out)。

该样例和样例 1 相同，只是 $x_{3}=9$；因此第二辆卡车在第 $4$ 秒时减速，而 Bajtazar 在第 $\frac{16}{3}$ 秒时换到右边车道，然后立刻换回左边车道。

样例 3

见附加文件下 [wyp2.in](file:wyp2.in) 和 [wyp2.out](file:wyp2.out)。

该样例满足 $n=100$，并且对于每辆卡车 $i$，我们有：$x_{i}=(n+1) \cdot i, d_{i}=i$ 且 $v_{i}=1$。Bajtazar 以 $2$ 的速度行驶，他的车长为 $50$。

样例 4

见附加文件下 [wyp3.in](file:wyp3.in) 和 [wyp3.out](file:wyp3.out)。

该样例满足 $n=200$。最初所有的车辆（包括 Bajtazar）都是车头对车尾地行驶。Bajtazar 以 $300$ 的速度行驶，而接下来的卡车以 $1,2, \ldots, n$ 的速度行驶。Bajtazar 的车长为 $1$，而每辆卡车的车长为 $2$。

样例 5

见附加文件下 [wyp4.in](file:wyp4.in) 和 [wyp4.out](file:wyp4.out)。

该样例满足 $n=100$，并且对于每辆卡车 $i$，我们有 $x_{i}=101 \cdot i, d_{i}=1$ 且 $v_{i}=n-i+1$。Bajtazar 的车长为 $1$，以 $1000$ 的速度行驶。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	额外限制	分值
$1$	所有的 $v_{i}$ 都相等	$10$
$2$	数列 $v_{i}$ 是非递减的 $(v_{i} \leq v_{i+1})$	$20$
$3$	$n \leq 1000$	$35$
$4$	无额外限制	$35$