Problem G
Banana Problem

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?

Input

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

Output a single integer — the number of bananas that the monkeys eat, following Gon’s strategy.

Explanation of Sample input

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$.

1 2 0 2
2 1000
1 1 1 2
1 2 2 1

1

2 2 1 2
1 1 2 1
1 2
2 1
1 2 3 1
2 2 2 3

1