Gon is playing the game ‘Greedy Monkeys’.
The game is setup as follows:
There are $N$ ladders, numbered from $1$ to $N$. Each ladder has height $H$, and has $H + 1$ steps at height $0, 1 \ldots , H$. Let $(\ell , h)$ represent the step at height $h$ of the $\ell $-th ladder.
There are $R$ horizontal ropes. Each rope connects two steps at the same height of two different ladders. The ropes are numbered from $1$ to $R$, and the $i$-th rope’s length is $b_ i$. No rope is connected to any $0$-th or $H$-th step of any ladders. A step in a ladder has at most one rope connected to it.
There are $B$ special positions, numbered from $1$ to $B$. The $i$-th position is parameterized by $4$ integers $\ell _ i$, $h_ i$, $x_ i$ and $y_ i$, where $1 \leq \ell _ i \leq N$ and $1 \leq h_ i \leq H$. For every non-negative integer $t$:
At time $t \cdot (x_ i + y_ i) + 0.5$, a new banana appears at position $(\ell _ i, h_ i)$.
At time $t \cdot (x_ i + y_ i) + x_ i + 0.5$, this banana disappears from position $(\ell _ i, h_ i)$.
For example, if $x_ i = 2$ and $y_ i = 3$: a banana appears at $0.5$ and disappears at $2.5$. Then a different banana appears at $5.5$ and disappears at $7.5$, and so on. It is guaranteed that no rope is connected to a special location. All special locations are distinct.
At the beginning of the game, there are $N$ monkeys, numbered from $1$ to $N$. The $i$-th monkey stands at $(i, 0)$. It takes the $i$-th monkey $c_ i$ seconds to climb up one step of any ladders, and $d_ i$ seconds to move one unit along any ropes.
A monkey can eat a banana if and only if the monkey is at the same position as the banana, and the banana has not yet disappeared. It takes a monkey a negligible amount of time to eat a banana. Naturally, a banana can only be eaten once. If multiple monkeys is at the same position as a banana at the same time, only one monkey can eat that banana. However, if monkeys arrive at a special location multiple times, they may eat more than one banana in this location.
The player needs to control the monkeys. As Gon is a simple boy, he controls the monkeys using a very simple strategy:
If a monkey is at a step of a ladder connected to a rope, and the monkey has not moved along this rope in either directions, it will immediately start moving along the rope towards the other end.
Otherwise, the monkey will move up the ladder.
The monkeys always move according to the above two rules, unless they can no longer moves (which happens only when they reach the $H$-th step of some ladders).
The monkeys can freely pass through each other.
How many bananas will the monkeys eat, if Gon follows this strategy?
The first line of input contains $4$ integers $N$, $H$, $R$ and $B$ $(1 \le N \le 3 \cdot 10^5, 0 \le R, B \le 3 \cdot 10^5, 1 \le H \le 10^9)$ — the number of ladders, the height of each ladder, the number of ropes and the number of special locations.
In the next $R$ lines, the $i$-th line contains $4$ integers $b_ i$, $\ell _{1,i}$, $\ell _{2,i}$ and $s_{i}$ $(1 \le b_ i \le 10^4, 1 \le \ell _{1,i}, \ell _{2,i} \le N, \ell _{1,i} \ne \ell _{2,i}, 1 \le s_{i} < H)$, meaning that the $i$-th rope has length $b_ i$ and connects two positions $(\ell _{1,i}, s_{i})$ and $(\ell _{2,i}, s_{i})$.
In the next $N$ lines, the $i$-th line contains $2$ integers $c_ i$ and $d_ i$ $(1 \le c_ i, d_ i \le 10^4)$ — the number of seconds it takes for a monkey to move up one step of some ladder, and move one unit along some rope.
In the next $B$ lines, the $i$-th line contains $4$ integers $\ell _ i$, $h_ i$, $x_ i$ and $y_ i$ $(1 \le \ell _ i \le N, 1 \le h_ i \le H, 1 \le x_ i, y_ i \le 10^4)$ — where $(\ell _ i, h_ i)$ is the position of the $i$-th special location. $x_ i$ and $y_ i$ are its parameters.
It is guaranteed that:
Each position is connected to at most one rope.
All special positions, where bananas appear, are distinct.
Special positions are not connected to any ropes.
Output a single integer — the number of bananas that the monkeys eat, following Gon’s strategy.
In the first example:
There is only $1$ ladder and no ropes.
The monkey initially stands at $(1, 0)$. It takes $2$ seconds for the monkey to move up one step of a ladder.
There are $2$ special locations:
The first special location is at $(1, 1)$. A banana appears at time $0.5$, disappears at time $1.5$. Another banana appears at time $3.5$, disappears at time $4.5$, and so on.
The second special location is at $(1, 2)$. A banana appears at time $0.5$, disappears at time $2.5$. Another banana appears at time $3.5$, disappears at time $5.5$, and so on.
The monkey arrives at $(1, 1)$ at time $2$. There is no banana at $(1, 2)$ at this time.
The monkey arrives at $(1, 2)$ at time $4$. The monkey eats $1$ banana here.
Thus, the answer is $1$.
In the second example:
There are $2$ ladders, and $1$ rope connecting $(1, 1)$ and $(2, 1)$ with length $1$.
The first monkey is initially at $(1, 0)$. It will be at:
$(1, 1)$ at time $1$,
$(2, 1)$ at time $3$,
$(2, 2)$ at time $4$.
The second monkey is initially at $(2, 0)$. It will be at:
$(2, 1)$ at time $2$,
$(1, 1)$ at time $3$,
$(1, 2)$ at time $5$.
There are $2$ special locations:
The first special location is at $(1, 2)$. There is a banana from $0.5$ to $3.5$, another banana from $4.5$ to $7.5$ and so on.
The second special location is at $(2, 2)$. There is a banana from $0.5$ to $2.5$, another banana from $5.5$ to $7.5$ and so on.
The second monkey can eat the banana at the first special location, and the first monkey can not eat any banana.
Thus, the answer is $1$.
Sample Input 1 | Sample Output 1 |
---|---|
1 2 0 2 2 1000 1 1 1 2 1 2 2 1 |
1 |
Sample Input 2 | Sample Output 2 |
---|---|
2 2 1 2 1 1 2 1 1 2 2 1 1 2 3 1 2 2 2 3 |
1 |