题目描述
小爱和她的朋友小艾正在进行赛车游戏。她们从同一个起点,同一方向,同时出发。每个人在比赛中的速度可以被分为若干个**阶段**。在每个**阶段**里,小爱或小艾的速度是不变的。
由于车手的速度有变化,会出现**超车**的现象。所谓**超车**,就是指原本位置落后的一人,通过较快的速度实现了位置的超前。判定是否**超车**,关键看两人的相对位移是否从正变负(或从负变正)。在起点位置,因两人相对位置只是从 $0$ 变成了正数,所以不算发生**超车**。
给定小爱和小艾在每个**阶段**的速度和持续时间,请统计一下,在比赛的过程中,出现了多少次**超车**现象。
输入
第一行:两个整数 $n$ 和 $m$
+ $n$ 表示小爱的赛车进程分为 $n$ 个阶段;
+ $m$ 表示小艾的赛车进程分为 $m$ 个阶段。
接下来 $n$ 行:每行表示小爱进程中的一个阶段,有两个整数 $t_i$ 和 $v_i$,表示该阶段中,小爱的速度为 $v_i$,持续时间为 $t_i$。
接下来 $m$ 行:每行表示小艾进程中的一个阶段,有两个整数 $s_i$ 和 $w_i$,表示该阶段中,小艾的速度为 $w_i$,持续时间为 $s_i$。
保证两人赛车的总距离是相等的,即保证
$$v_1t_1+v_2t_2+\cdots+v_nt_n=w_1s_1+w_2s_2+\cdots+w_ms_m$$
输出
单个整数:表示在整个比赛过程中,共计出现了多少次超车**现象**。
样例输入输出
输入#1
复制
2 3
10 10
2 50
4 15
8 15
1 20
提示
记 $L=v_1t_1+v_2t_2+\cdots+v_nt_n$,
+ 对于 $30\%$ 的数据,$1\leq n, m\leq 100$,$1\leq L\leq 10000$;
+ 对于 $60\%$ 的数据,$1\leq n, m\leq 1000$,$1\leq L\leq 10^7$;
+ 对于 $100\%$ 的数据,$1\leq n, m\leq 10^5$,$1\leq L\leq 10^9$;