Speeding Ticket#11155

Speeding Ticket

1 second

128 megabytes

Very easy

Always the troublemaker, Bessie the cow has stolen Farmer John's tractor and taken off down the road!

The road is exactly $100$ miles long, and Bessie drives the entire length of the road before eventually being pulled over by a police officer. The officer gives Bessie a ticket for exceeding the speed limit, for having an expired license, and for operating a motor vehicle while being a cow. While Bessie concedes that the last two tickets are probably valid, she questions whether the officer was correct in issuing the speeding ticket. She wants to determine for herself whether she actually exceeded the speed limit at any point during her journey.

The road is divided into $n$ segments. Each segment is described by a positive integer length in miles and an integer speed limit in the range $1...100$ miles per hour. Since the road is $100$ miles long, the lengths of all $n$ segments add up to $100$ . For example, the road might begin with a segment of length $45$ miles and a speed limit of $70$ miles per hour, followed by a segment of length $55$ miles with a speed limit of $60$ miles per hour.

Bessie's journey can also be described as a series of $m$ segments. During each segment, she travels a certain positive integer number of miles at a constant integer speed. For example, she might begin by traveling $50$ miles at a speed of $65$ miles per hour, followed by another $50$ miles at a speed of $55$ miles per hour. The lengths of all $m$ segments add up to $100$ miles in total. Farmer John's tractor can travel at a maximum speed of $100$ miles per hour.

Given this information, determine the maximum amount by which Bessie's speed exceeds the speed limit at any point during her journey.

Input

The first line contains two integers $n$ and $m$ . The next $n$ lines each contain two integers describing a road segment: its length and speed limit.

The next $m$ lines each contain two integers describing a segment of Bessie's journey: its length and the speed at which Bessie was driving.

Output

Print one integer — the maximum amount by which Bessie's speed exceeded the speed limit at any point during her journey. If she never exceeds the speed limit, print $0$ .

Examples

In this example, the road consists of three segments: $40$ miles at $75$ miles per hour, followed by $50$ miles at $35$ miles per hour, and then $10$ miles at $45$ miles per hour. Bessie drives through three segments: $40$ miles at $76$ miles per hour, $20$ miles at $30$ miles per hour, and $40$ miles at $40$ miles per hour. During her first segment, she is only slightly over the speed limit, but her last segment results in the most serious violation, with Bessie exceeding the speed limit by $5$ miles per hour for part of the journey. Therefore, the correct answer is $5$ .

Example 1