Description

SH's running performance has not been ideal.

To help SH improve, KC decides to have a race with him.

The starting point is set in front of the farmer's house. They start at the same time, run in the same direction, and finish under a tree far away on the farm.

Their running speeds are constant over some time segments. For example, SH runs at speed $5$ for the first $3$ time segments, then at speed $10$ for the next $6$ time segments.

Their total race time is the same.

They want to count how many times the leading order changes over the entire race.

For example, if at some moment SH is leading, and at the next moment KC is leading, that counts as one change in the leading order; if at some moment SH is leading, then over a period KC catches up and runs neck and neck and eventually overtakes SH, that also counts as one change.

Input Format

Line $1$: two integers $N, M$.

The next $N$ lines: each line has two integers describing one segment of SH's run, representing SH's speed in that segment and the duration of maintaining that speed.

The next $M$ lines: each line has two integers describing one segment of KC's run, representing KC's speed in that segment and the duration of maintaining that speed.

All input numbers are positive integers not greater than $1000$.

Output Format

One line: the number of changes in the leading order during the entire race.

4 3
1 2
4 1
1 1
2 10
2 3
1 2
3 9

2

Hint

Sample explanation:

SH runs at speed $1$ for the first $2$ time units, then at speed $4$ for $1$ time unit, then at speed $1$ for $1$ time unit, and finally at speed $2$ for $10$ time units. KC runs at speed $2$ for the first $3$ time units, then at speed $2$ for $2$ time units, and finally at speed $3$ for $9$ time units.

After the race starts, KC leads until the $5$th time unit, when SH overtakes KC (the first change in the leading order). Then at the $7$th time unit, KC overtakes SH and becomes the leader again (the second change in the leading order).

Translated by ChatGPT 5