超速罚单

题目描述

麻烦制造者贝茜偷了农夫约翰的拖拉机上路狂飙。

公路共 $100$ 英里长，在驾车行驶了整条路后，她被交警拦下了。

警察给贝茜开了三张罚单，分别对应超速，驾照过期以及驾驶者是头牛。

虽然贝茜承认最后两张罚单可能是有效的，但是她对超速罚单表示质疑。

她想自己确定自己是否在部分行程中确实超速行驶。

这条路被分为了 $N$ 段，每段都由一个正整数长度以及一个不超过 $100$ 的正整数限速（单位：英里/小时）来描述。

由于公路一共长 $100$ 英里，因此，这 $N$ 段长度之和也为 $100$ 英里。

例如，公路可能分 $2$ 段，第 $1$ 段长 $45$ 英里，限速 $70$（单位：英里/小时），第 $2$ 段长 $55$ 英里，限速 $60$（单位：英里/小时）。

贝茜的行程可以被分成 $M$ 段，每段行程中，她以一定的整数速度行驶一定的正整数英里数。

所有 M 段行程的长度之和为 100 英里。

例如，她可能先以 $65$（单位：英里/小时）的速度行驶 50 英里，然后再以 $55$（单位：英里/小时）的速度行驶 $50$ 英里。

约翰的拖拉机最高速度可达到 $100$（单位：英里/小时）。

根据上述信息，请确定贝茜在行驶过程中的最大超速是多少。

输入格式

第一行包含整数 $N$ 和 $M$。

接下来 $N$ 行，每行包含两个整数，描述一个路段的长度和限速。

接下来 $M$ 行，每行包含两个整数，描述贝茜的旅途中的一个路段的长度和行驶速度。

输出格式

输出贝茜在行驶过程中的最大超速。

如果全程无超速，则输出 $0$。

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

5

提示

#### 数据范围 $1\le N,M\le 100$

样例解释

在此样例中，公路共分为 $3$ 段，前 $40$ 英里限速 $75$，中间 $50$ 英里限速 $35$，最后 $10$ 英里限速 $45$。

贝茜在行程中，前 $40$ 英里速度为 $76$，中间 $20$ 英里速度为 $30$，最后 $40$ 英里速度为 $40$。

由上可得，贝茜行驶的前 $40$ 英里超速 $1$，第 $60$ 到 $90$ 英里超速 $5$，其他过程无超速。

所以，贝茜的最大超速为 $5$。

来源

童程童美