Background

This problem is translated from POI2022~2023R1 wyp。

Problem Description

You are driving your newly bought car on a highway. The highway has $2$ lanes (left and right). Initially, all vehicles are in the right lane. There are $n$ cars in front of you, but they are too slow, so you want to overtake them.

Your speed is $V$, and the speed of the $i$-th other car is $v_i$ (it is guaranteed that $V > v_i$). If the front of your car is about to crash into another car, you will steer left to overtake. If, at your current position, there is a gap on the right lane that allows your car to move into it, then you will definitely move to the right.

Note that collisions between other cars may happen. After a collision, the speed of the car behind will change to be the same as the speed of the car in front of it.

Determine how many times your car will make a left-turn operation.

Input Format

The first line contains four integers $n$, $D$, $W$, $M$ ($1 \leq n \leq 10^5$, $1 \leq D \leq 10^9$, $1 \leq W,M \leq 1000$), representing the number of trucks, the length of your car, your car’s speed $W/M$, and it is assumed that the coordinate of the front of your car is $0$.

The next $n$ lines each contain four integers $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$), representing the position, length, and speed $w_i / m_i$ of the other cars.

It is guaranteed that the input is given in increasing order of $x_i$.

Output Format

Output the number of left turns needed to overtake $n$ cars.

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

2

Hint

Explanation of the sample:

The subtasks are as follows:

In this problem, subtask $0$ is the sample.

Translated by ChatGPT 5