麻烦制造者贝茜偷了农夫约翰的拖拉机上路狂飙。
公路共 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。
1≤N,M≤100
3 3
40 75
50 35
10 45
40 76
20 30
40 40
5
在此样例中,公路共分为 3 段,前 40 英里限速 75,中间 50 英里限速 35,最后 10 英里限速 45。
贝茜在行程中,前 40 英里速度为 76,中间 20 英里速度为 30,最后 40 英里速度为 40。
由上可得,贝茜行驶的前 40 英里超速 1,第 60 到 90 英里超速 5,其他过程无超速。
所以,贝茜的最大超速为 5。