Question 4

Text from the official booklet. Refer to the PDF for original mathematical notation, formatting, and linked input files. Printed samples and inputs are reproduced as published.

A driver is traveling along a straight 100-mile road, which is divided into 𝑁 segments. Each
segment has a specified length (in miles) and a speed limit (between 1 and 100 miles per hour).
The total length of all segments adds up to exactly 100 miles.
The driver’s journey is also divided into 𝑀 segments, where each segment specifies how many
miles they traveled and at what speed. The sum of all journey segments is also exactly 100
miles. The vehicle used can reach a maximum speed of 100 miles per hour.
Your task is to determine the maximum amount by which the driver exceeded the speed limit at
any point during the journey.
Input format:
The first line of the input contains N and M, separated by a space.
The next N lines each contain two integers describing a road segment, giving its length and
speed limit.
The next M lines each contain two integers describing a segment in the driver’s journey, giving
the length and also the speed at which the driver was driving.
Output format:
Please output a single line containing the maximum amount over the speed limit the driver
drove during any part of the journey. If the driver never exceeds the speed limit, please output 0.
SAMPLE INPUT:
3 3
40 75
50 35
10 45
40 76
20 30
40 40
SAMPLE OUTPUT:
5
Input
Case 1:
50 50
1 35
2 74
2 44
1 36
1 4
1 39
4 98
1 78
1 65
2 58
1 26
2 91
1 53
1 87
2 69
1 72
3 5
2 59
7 75
1 44
1 54
5 99
1 25
1 76
3 43
2 42
4 15
1 14
2 44
2 59
1 17
1 51
1 55
4 30
2 51
1 91
2 3
1 32
4 66
3 49
2 34
4 31
2 97
2 20
2 87
3 90
1 74
1 48
2 71
2 24
1 50
3 54
2 30
1 4
3 19
6 42
1 12
2 95
1 43
6 1
2 2
2 8
1 66
1 70
2 23
1 68
2 44
3 42
1 78
3 3
2 22
1 15
1 20
2 17
1 10
2 10
1 7
1 14
1 33
2 9
4 11
2 24
2 21
3 31
2 2
5 15
1 30
1 25
3 40
1 18
4 22
1 54
2 8
1 69
1 57
2 22
2 61
3 19
1 12
1 32
Case 2:
100 100
1 57
1 14
1 37
1 100
1 69
1 19
1 97
1 74
1 66
1 98
1 77
1 38
1 4
1 97
1 39
1 74
1 51
1 72
1 68
1 62
1 66
1 26
1 65
1 10
1 99
1 1
1 91
1 59
1 59
1 96
1 19
1 66
1 8
1 50
1 69
1 17
1 57
1 57
1 32
1 57
1 10
1 52
1 67
1 28
1 77
1 43
1 27
1 40
1 76
1 34
1 81
1 63
1 56
1 80
1 37
1 17
1 9
1 14
1 15
1 46
1 11
1 97
1 37
1 64
1 37
1 80
1 73
1 81
1 43
1 77
1 96
1 37
1 57
1 14
1 95
1 47
1 90
1 15
1 30
1 92
1 99
1 26
1 38
1 56
1 25
1 77
1 7
1 35
1 88
1 11
1 62
1 71
1 56
1 26
1 34
1 16
1 63
1 37
1 82
1 88
1 67
1 8
1 29
1 3
1 48
1 13
1 69
1 19
1 7
1 18
1 55
1 27
1 1
1 22
1 5
1 50
1 19
1 36
1 40
1 34
1 14
1 4
1 16
1 8
1 18
1 1
1 72
1 46
1 43
1 29
1 7
1 18
1 8
1 42
1 48
1 16
1 56
1 52
1 7
1 16
1 2
1 2
1 19
1 5
1 51
1 29
1 11
1 21
1 20
1 18
1 52
1 58
1 38
1 67
1 31
1 5
1 7
1 5
1 6
1 14
1 4
1 81
1 32
1 15
1 13
1 3
1 67
1 43
1 28
1 34
1 23
1 26
1 29
1 2
1 74
1 32
1 29
1 14
1 30
1 31
1 91
1 7
1 5
1 17
1 12
1 54
1 12
1 14
1 9
1 9
1 40
1 11
1 12
1 12
1 7
1 6
1 44
1 18
1 1
1 100