1547 - 【USACO】greetings

通过次数

26

提交次数

55

时间限制 : 1 秒
内存限制 : 128 MB

众所周知,奶牛是一种非常具有社交礼仪的生物,任何时候两只奶牛在分开后相遇,她们会友好的向对方用 “moo” 来问候。

奶牛 Bessie 和她的好朋友 Elsie 正在围绕 Farmer John 农场的长路上走着。简单起见,我们可以将这条路看作是一维的数轴。 Bessie 和 Elsie 同时从原点出发,并且以相同的速度行走一段时间。给出每只奶牛的移动描述,请计算出它们互相用 “moo” 问候了多少次。

Bessie 和 Elsie 可能在不同的点停止移动,并且每只奶牛不会行走超过 10^6 个时间单位。

输入

1 行: 两个用空格隔开的整数 B1 ≤ B ≤ 50000 )和 E1 ≤ E ≤ 50000 )。

2 \dots 1 + B 行:这 B 行描述 Bessie 的移动。每行包含一个正整数和一个 L 或者 R ,表示 Bessie 移动的距离,以及方向是左或者右。

2 + B \dots 1 + B + E 行:这 E 行描述 Elsie 的移动。每行包含一个正整数和一个 L 或者 R ,表示 Elsie 移动的距离,以及方向是左或者右

输出

1 行:一个整数表示两只奶牛问候 “moo” 的次数。她们初始时同时在原点没有用 “moo” 进行问候。

样例

输入

4 5
3 L
5 R
1 L
2 R
4 R
1 L
3 L
4 R
2 L

输出

3

提示

Bessie 向左移动 3 个时间单位,然后向右移动 5 个时间单位,然后向左移动 1 个时间单位,最后向右移动 2 个时间单位,然后停止不动。

Elsie 向右移动 4 个时间单位,然后向左移动 1 个时间单位,然后向左移动 3 个时间单位,然后向右移动 4 个时间单位,最后向左移动 2 个时间单位,然后停止不动。

Bessie 和 Elsie 分别在时刻 7913 进行了暂别后相遇的问候。

来源

USACO