{"problem":{"name":"[COCI 2009/2010 #6] GREMLINI","description":{"content":"有 $n$ 种小妖精，我们给这 $n$ 类小妖分别编号为 $1,\\dots,n$。 $t$ 年前，一次事故造出了 $n$ 只小妖（视为刚出生的，而非成熟的），这些小妖的种类互不相同。 第 $i$ 种小妖出生后需要 $y_i$ 年成熟，成熟后会立即产下 $k_i$ 个蛋（小妖是无性繁殖的生物）然后死亡。将它的蛋编号为 $1.\\dots,k$，其中，第 $j$ 个蛋需要 $h_{i,j}$ 年孵化","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":32768},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8408"},"statements":[{"statement_type":"Markdown","content":"有 $n$ 种小妖精，我们给这 $n$ 类小妖分别编号为 $1,\\dots,n$。\n\n$t$ 年前，一次事故造出了 $n$ 只小妖（视为刚出生的，而非成熟的），这些小妖的种类互不相同。\n\n第 $i$ 种小妖出生后需要 $y_i$ 年成熟，成熟后会立即产下 $k_i$ 个蛋（小妖是无性繁殖的生物）然后死亡。将它的蛋编号为 $1.\\dots,k$，其中，第 $j$ 个蛋需要 $h_{i,j}$ 年孵化，孵出的小妖的类型为 $g _ {i, j}$。\n\n请问，现在和祖先关系最远的小妖到了多少代，不考虑暂未孵出的。假设祖先是 $0$ 代，其子辈为第 $1$ 代，孙辈为第 $2$ 代，以此类推。\n\n## Input\n\n第一行：$n,t$。\n接下来 $3n$ 行，每三行为一组。\n\n每组的第一行：$k_i,y_i$。\n每组的第二行：$g_{ i,1},\\ldots,g_{i,k_i}$。\n每组的第三行：$h_{ i,1},\\ldots,h_{i,k_i}$。\n\n## Output\n\n一行，一个整数，表示现在和祖先关系最远的小妖到了多少代。\n\n[samples]\n\n## Note\n\n**【样例 #1 解释】**\n\n事故发生 $10$ 年后，最开始的那只小妖（$0$ 代）产下了一个蛋，然后死亡。事故发生 $15$ 年后，蛋孵化出了新的一只小妖（$1$ 代）。事故发生 $25$ 年后，$1$ 代小妖产下了一个蛋，然后死亡。事故发生 $30$ 年后，蛋孵化出了新的一只小妖（$2$ 代）。事故发生 $40$ 年后，$2$ 代小妖产下了一个蛋，然后死亡。事故发生 $42$ 年后，这个蛋仍未孵化，因此不计。\n\n**【数据范围】**\n\n$1 \\le n \\le 100,1 \\le t \\le 10^{15},1 \\le k_i, y_i, h_{i,j} \\le 1000,1 \\le g_{i,j} \\le n$。\n\n本题分值按 COCI 原题设置，满分 $130$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8408","tags":["2009","矩阵乘法","COCI（克罗地亚）"],"sample_group":[["1 42\n1 10\n1\n5","2"],["2 42\n1 10\n1\n5\n1 5\n1\n5","3"],["3 8\n4 5\n1 2 3 2\n1 2 1 3\n1 1\n3\n1\n2 1\n1 2\n2 1","4"]],"created_at":"2026-03-03 11:09:25"}}