题目
总是惹事生非的奶牛贝西偷走了农夫约翰的拖拉机,沿着路跑了!
这条路正好有100英里长,贝西开了整整一段路,最后被一名警察拦了下来。警察给了贝西一张罚单,理由是她超速行驶,驾照过期,还因为她作为牛居然开了一辆机动车。虽然贝西承认最后两张罚单可能是有效的,但她质疑警官开超速罚单的做法是否正确,她想亲自确定自己是否确实在旅途中超速行驶了一段时间。
这条路被分成N段,每段都用一个以英里为单位的正整数长度来描述,以及1…100英里/小时范围内的整数限速。由于这条路有100英里长,所有N段的长度加起来等于100。例如,这条路可能从一段45英里的长度开始,限速70英里,然后可能以一段55英里的长度结束,限速60英里。
贝西的旅程也可以用一系列的片段来描述,M个片段。在每一段中,她以一定的整数速度,以一定的正整数英里的速度行进。例如,她可能开始以65英里的速度行驶50英里,然后以55英里的速度再行驶50英里。所有M段的长度加起来等于100英里。农民约翰的拖拉机能以每小时100英里的最快速度行驶。
根据以上信息,请确定贝茜在旅途中的任何一段行程中超过限速的最大数量。
输入
输入的第一行包含N和M,用空格分隔。
接下来的N行每一行包含两个整数,描述一个路段,给出它的长度和速度限制。
接下来的M行每一行都包含两个整数,它们描述了贝西旅程中的一段,给出了贝西行驶的长度和速度。
输出
请输出一行,包含贝茜在旅途中任何一段所驾驶的最大超速量。如果她从来没有超过速度限制,请输出0。
样例解释
在这个例子中,道路包含三个部分(40英里,75英里/小时,然后是50英里,35英里/小时,然后是10英里,45英里/小时)。贝茜分三段开车(40英里,每小时76英里,20英里,每小时30英里,40英里,40英里每小时)。在她的第一段比赛中,她的速度略高于限速,但她的最后一段比赛是最严重的违规,在其中一部分比赛中,她的速度超过限速5英里每小时。因此正确答案是5。