Description
为了决定出谁是农场上跑的最快的牛,奶牛Bessie和她的朋友Elsie决定在农场上举行一场比赛。两头奶牛从同一位置,同一时间,朝相同的方向开始跑。
每头奶牛的整个跑步过程可以看做是多个"区间段",每个区间段内奶牛的跑步的速度是一样的。比如,Bessie以5的速度跑了3个单位的时间,然后以速度10跑了6个单位的时间。整个过程中Bessie和Elsie跑的总时间是相同的。
请帮助奶牛们计算出,在比赛的过程中领跑者变化的数量是多少?
领跑者变化的意思是:例如在跑步的过程中刚开始是奶牛B领先的,然后在某个时间点奶牛A跑到了奶牛B的前面成了领先者,那么这就是一次领跑者变化。另外如果奶牛B处于领先位置,然后A在一段时间内与B是并行的,最终A领先了,那么这也算作是领跑者变化了。
Input
第一行,两个整数N和M(1≤N,M≤1000)
接下来N行,描述奶牛Bessie在比赛过程中的N个区间段,每行两个整数x和y,表示在区间段i内,Bessie以速度x跑了y单时间,整数的范围都是1到1000
接下来M行,描述奶牛Elsie在比赛过程中的N个区间段,每行两个整数x和y,表示在区间段i内,Elsie以速度x跑了y单时间,整数的范围都是1到1000
Output
输出一行,一个整数,表示在比赛期间领跑者变化的总数量
4 3
1 2
4 1
1 1
2 10
2 3
1 2
3 9
HINT
【样例说明】:
Bessie先以1的速度跑了2单位时间,然后以4的速度跑了1单位时间,然后以1的速度跑了1单位时间,最后以2的速度跑了10单位时间。
Elsie先以2的速度跑了3单位时间,然后以1的速度跑了2单位时间,最后以3的速度跑了9单位时间。
在整个过程中,刚开始Elsie领先,在时间t=3时,两头奶牛相遇,此时都跑了6单位的总距离,然后并行的跑了1单位的时间,然后Bessie领先了(第一次领跑者改变),短暂的领先后又被Elsie赶超了(第二次领跑者改变),然后Elsie一直领先直到比赛结束。
所以比赛期间领跑者一共变化了2次,输出答案是2.