#2970. 「COCI 2010.03.20」GREMLINI

内存限制:256 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

译自 COCI 2010.03.20 T6「GREMLINI

N 种小妖精,我们给这 N 类小妖分别编号为 1\ldots N

T 年前,一次事故造出了 N 只小妖(视为刚出生的,而非成熟的),这些小妖的种类互不相同。

i 种小妖出生后需要 Y_{\small i} 年成熟,成熟后会立即产下 K_{\small i} 个蛋(小妖是无性繁殖的生物)然后死亡。将它的蛋编号为 1\ldots K_{\small i} ,其中,第 j 个蛋需要 H_{\small i,j} 年孵化,孵出的小妖的类型为 G_{\small i,j}

请问,现在和祖先关系最远的小妖到了多少代,不考虑暂未孵出的。假设祖先是 1 代,其子辈为第 2 代,孙辈为第 3 代,以此类推。

输入格式

第一行: N,T
接下来 3N 行,每三行为一组。

  • 每组的第一行: K_{\small i},Y_{\small i}
  • 每组的第二行: G_{\small i,1}\ldots G_{\small i,K_i}
  • 每组的第三行: H_{\small i,1}\ldots H_{\small i,K_i}

输出格式

一行,一个整数,表示现在和祖先关系最远的小妖到了多少代。

样例

样例输入 1

1 42
1 10
1
5

样例输出 1

2

样例输入 2

2 42
1 10
1
5
1 5
1
5

样例输出 2

3

样例说明 2

事故发生 10 年后,最开始的那只小妖(1 代)产下了一个蛋,然后死亡。
事故发生 15 年后,蛋孵化出了新的一只小妖(2 代)。
事故发生 25 年后,2 代小妖产下了一个蛋,然后死亡。
事故发生 30 年后,蛋孵化出了新的一只小妖(3 代)。
事故发生 40 年后,3 代小妖产下了一个蛋,然后死亡。
事故发生 42 年后,这个蛋仍未孵化,因此不计。

样例输入 3

3 8
4 5
1 2 3 2
1 2 1 3
1 1
3
1
2 1
1 2
2 1

样例输出 3

4

数据范围与提示

1 ≤ N ≤ 100, 1 ≤ T ≤ 10^{15}, 1 ≤ K_i, Y_i, H_{\small i,j} ≤ 1000, 1 ≤ G_{\small i,j} ≤ N