Count Lead Changes in a Race

SH's running performance isn’t ideal. To help him improve, KC challenges him to a race. The race starts from the farmhouse door and ends under a tree in the distance. Both runners start at the same time and run in the same direction. Their speeds are constant within given time intervals. For example, SH might run at speed 5 for the first 3 time units and then at speed 10 for the next 6 time units. Similarly, KC has his own segments. The total race time for both is the same.

Your task is to count the number of times the lead change occurs during the race. A lead change is counted whenever the effective leader switches from one runner to the other. More formally, if at one moment runner A is ahead and later runner B overtakes A (even if for some time they run neck‐to‐neck), that counts as one lead change. Mathematically, if we denote the difference in positions as \(d(t)=\text{pos}_{SH}(t)-\text{pos}_{KC}(t)\), a crossing (with a change in sign of \(d(t)\)) indicates that a lead change has occurred (ignoring tie moments).

inputFormat

The input begins with an integer \(n\) (the number of segments for SH). The following \(n\) lines each contain two integers: the duration and the speed for that segment.

Next, an integer \(m\) is given (the number of segments for KC), followed by \(m\) lines each containing two integers: the duration and the speed for that segment.

It is guaranteed that the total time for SH and KC are equal.

outputFormat

Output a single integer representing the number of lead changes during the race.

sample

2
3 5
6 10
2
3 10
6 5

1