Speed Violation
InterviewTime limit2sMemory limit512 MB
Two speed profiles split the same 100 km road at different points, and you report the largest amount by which the driven speed exceeds the limit.
- Level
Easy2 of 10
- Topics
- Two pointers, Simulation
- Solved
- No attempts yet
Problem
Yeonjeong takes Taewoo's car without asking and drives down the road. The road is exactly 100 km long and she drives all the way to the end. She pays no attention to the posted limits and drives at whatever speed she likes.
The road is split into N sections. Each section comes with its length and its speed limit. The N lengths add up to 100 km, and every length and every speed limit is a positive integer. For example, if N is 3 and the sections are (40, 75), (50, 35), (10, 45) in order, the first section is 40 km long with a limit of 75 km/h, the second is 50 km long with a limit of 35 km/h, and the third is 10 km long with a limit of 45 km/h.
The record of her drive is split into M sections. Each section comes with its length and the speed she held over it. The M lengths also add up to 100 km, and every length and every speed is a positive integer.
The two splits do not have to break at the same points. At a point on the road, the amount she is over is her speed at that point minus the limit at that point, and a value of 0 or less is not a violation. Find the largest amount she is over the limit anywhere along the 100 km.
Input
The first line contains N and M. Each of the next N lines contains the length of a speed limit section and that section's speed limit. Each of the following M lines contains the length of a section she drove and the speed she held over it.
Every value is a positive integer, and the lengths in each of the two splits sum to 100. Because every length is a positive integer, N and M are at most 100.
Output
Print the largest amount she is over the limit, on one line. Print 0 if she never goes over.
Hint
Suppose the limit sections are (40, 75), (50, 35), (10, 45) and the driven sections are (40, 76), (20, 30), (40, 40). From 0 km to 40 km she drives 76 km/h, which is 1 km/h over. From 60 km to 90 km she drives 40 km/h, which is 5 km/h over. She stays within the limit everywhere else, so the answer is 5.