Speeding Ticket

题目描述

一向爱惹麻烦的奶牛 Bessie 偷走了农夫 John 的拖拉机，沿着公路一路开走了！\n这条公路全长正好 100 英里，Bessie 开完全程后最终被警察拦下。警察给她开了三张罚单：超速、驾照过期、以及作为一头奶牛驾驶机动车。Bessie 承认后两张罚单大概没问题，但她怀疑警察在超速罚单上的判断是否正确，因此她想自己确认一下：在旅途中她是否有一段时间确实超过了限速。\n公路被分成 $N$ 段，每段用一个正整数表示长度（英里），以及一个范围为 $1 \ldots 100$（英里/小时）的整数限速描述。由于公路全长为 100 英里，$N$ 段的长度之和为 100。例如，公路可能先是一段 45 英里、限速 70，然后以一段 55 英里、限速 60 结束。\nBessie 的行程也可以被描述为 $M$ 段。在每一段中，她以某个正整数英里数行驶，并以某个整数速度行驶。例如，她可能先以 65 的速度行驶 50 英里，然后再以 55 的速度行驶 50 英里。$M$ 段的长度之和同样为 100 英里。农夫 John 的拖拉机最快能开到 100 英里/小时。\n给定以上信息，请确定在 Bessie 的整个行程中，她在任意时刻超过限速的最大幅度。

输入格式

第一行包含 $N$ 和 $M$，用空格分隔。\n接下来的 $N$ 行每行包含两个整数，描述一段公路：该段的长度和限速。\n接下来的 $M$ 行每行包含两个整数，描述 Bessie 行程中的一段：该段的长度以及 Bessie 的行驶速度。

输出格式

输出一行，包含 Bessie 在行程中任意时刻超过限速的最大值。如果她从未超过限速，请输出 0。

3 3\n40 75\n50 35\n10 45\n40 76\n20 30\n40 40

5

提示

在这个例子中，道路包含三段（40 英里、限速 75 英里/小时；接着 50 英里、限速 35 英里/小时；然后 10 英里、限速 45 英里/小时）。Bessie 行驶也分为三段（40 英里、速度 76 英里/小时；20 英里、速度 30 英里/小时；40 英里、速度 40 英里/小时）。在她的第一段中，她略微超速，但她最后一段的违规最严重，其中有一部分她比限速快了 5 英里/小时。因此正确答案是 5。\n题目贡献：Austin Bannister 和 Brian Dean

标签: USACO|2015|Bronze

来源

USACO|2015|Bronze