← 返回题目列表

Codeforces · 43/E

E. 比赛

中文机器翻译题面 查看原题

今天的一公里长的汽车比赛在伯兰举行。赛道用一条长达 s 公里的直线表示。有n辆赛车参加比赛,所有赛车都在赛道的起点同时出发。每辆车的行为都是已知的——每个部分的系统,其中汽车的速度是恒定的。第 i 辆车的第 j 个路段是对 (vi, j, ti, j),其中 vi, j 是汽车在整个路段上的速度(以公里每小时为单位),ti, j 是汽车以该速度行驶了多少小时。这些路段按照汽车“行驶”的顺序给出。

您的任务是找出比赛期间某辆车领先另一辆车的次数。领先被认为是一辆车出现在另一辆车前面的情况。众所周知,所有线索都会立即发生,即。 e.不存在这样的正长度时间段,其中两辆车“一起”行驶。在某一时刻,同一点上可能会出现多条线索。在这种情况下,所有这些都应该单独进行。起点和终点的车辆相遇不被视为领先。

输入

第一行包含两个整数 n 和 s (2 ≤ n ≤ 100, 1 ≤ s ≤ 106) — 汽车数量和轨道长度(以公里为单位)。然后n行——每辆车的分段系统的描述。每个描述都以整数 k (1 ≤ k ≤ 100) 开始——系统中的段数。然后写入 k 个空格分隔的整数对。每对是该段的速度和时间。这些整数都是正数,不超过1000。保证每辆车所有路段的长度(以公里为单位)之和等于s;所有的线索都会立即发生。

输出

打印单个数字——某辆车在比赛中领先于另一辆车的次数。

示例

输入 #1

2 33
2 5 1 2 14
1 3 11

输出 #1

1

输入 #2

2 33
2 1 3 10 3
1 11 3

输出 #2

0

输入 #3

5 33
2 1 3 3 10
1 11 3
2 5 3 3 6
2 3 1 10 3
2 6 3 3 5

输出 #3

2