USACO 2015 December Contest, Bronze

问题 2：超速罚单

一直是麻烦制造者的贝西奶牛偷走了农场主约翰的拖拉机，驶下了路！ 这条路长恰好100英里，贝西驾驶了整个路程，最终被一名警察拦下，并因为超速、驾驶过期执照以及以奶牛身份驾驶机动车而被罚款。虽然贝西承认最后两个罚单可能是有效的，但她怀疑警察是否正确地开了超速罚单，她想自己确认在旅程的某个部分是否确实超速了。

这条路被分为 N 段，每段有一个正整数的长度（以英里为单位）以及一个介于 1 到 100 之间的速度限制。由于这条路的总长度是100英里，因此所有 N 段的总长度加起来为 100。例如，路可能开始时有一段 45 英里的路，速度限制为 70，接着可能有一段 55 英里的路，速度限制为 60。

贝西的旅程也可以通过 M 段来描述。在每段旅程中，她以某一固定速度行驶了某个正整数的英里数。例如，她可能开始时以 65 英里的速度行驶了 50 英里，然后以 55 英里的速度行驶了 50 英里。所有 M 段的总长度加起来也是 100 英里。农场主约翰的拖拉机最快能以 100 英里的时速行驶。

根据上述信息，请确定贝西在旅程中的任何一部分超速行驶的最大超速数。

输入格式（文件 speeding.in）：

• 第一行输入两个整数 N 和 M，分别表示路段的数量和贝西的旅程段数。
• 接下来的 N 行，每行包含两个整数，分别表示每个路段的长度和速度限制。
• 接下来的 M 行，每行包含两个整数，分别表示贝西行驶的每段长度和贝西行驶的速度。

输出格式（文件 speeding.out）：

输出一个整数，表示贝西在旅程中的任何部分超速的最大数值。如果贝西从未超速，输出 0。

样例输入：

3 3
40 75
50 35
10 45
40 76
20 30
40 40

样例输出：

5

解释：

在这个例子中，路由包含三段（40 英里速度限制 75 英里/小时，接着 50 英里速度限制 35 英里/小时，然后是 10 英里速度限制 45 英里/小时）。贝西行驶了三段（40 英里速度 76 英里/小时，20 英里速度 30 英里/小时，40 英里速度 40 英里/小时）。在她的第一段旅程中，速度略微超速，但她的最后一段超速最为严重，部分路程超速 5 英里/小时。因此，正确答案是 5。

思路：

1. ​输入处理​：首先获取路段的数量和贝西的行驶段数，然后分别读取各路段的速度限制和贝西的行驶情况。
2. ​模拟行驶​：模拟贝西的每一段行驶，检查她在每段路程上是否超过了对应路段的速度限制，计算超速的数量。
3. ​最大超速计算​：在每段路程中，比较贝西的速度和该路段的速度限制，计算超速的数量并更新最大值。

解题步骤：

1. 根据输入获取所有路段的速度限制和贝西的速度。
2. 对每一段路程，判断贝西是否超速，计算并记录每段路程的超速量。
3. 输出贝西在任何一段路程中最大超速的数值。