#2970. 「COCI 2010.03.20」GREMLINI

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

题目描述

译自 COCI 2010.03.20 T6「GREMLINI

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

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

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

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

输入格式

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

  • 每组的第一行:Ki,YiK_{\small i},Y_{\small i}
  • 每组的第二行:Gi,1Gi,KiG_{\small i,1}\ldots G_{\small i,K_i}
  • 每组的第三行:Hi,1Hi,KiH_{\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

事故发生 1010 年后,最开始的那只小妖(1 代)产下了一个蛋,然后死亡。
事故发生 1515 年后,蛋孵化出了新的一只小妖(2 代)。
事故发生 2525 年后,2 代小妖产下了一个蛋,然后死亡。
事故发生 3030 年后,蛋孵化出了新的一只小妖(3 代)。
事故发生 4040 年后,3 代小妖产下了一个蛋,然后死亡。
事故发生 4242 年后,这个蛋仍未孵化,因此不计。

样例输入 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

数据范围与提示

1N100,1 ≤ N ≤ 100, 1T1015,1 ≤ T ≤ 10^{15}, 1Ki,YiHi,j1000,1 ≤ K_i, Y_i, H_{\small i,j} ≤ 1000, 1Gi,jN1 ≤ G_{\small i,j} ≤ N