P8408 [COCI 2009/2010 #6] GREMLINI

There are $n$ types of gremlins. We number these $n$ types as $1,\dots,n$. $t$ years ago, an accident created $n$ gremlins (consider them newborn, not mature), and their types were all different. After a type $i$ gremlin is born, it needs $y_i$ years to mature. Once it matures, it immediately lays $k_i$ eggs (gremlins reproduce asexually) and then dies. Number its eggs as $1,\dots,k_i$. The $j$-th egg needs $h_{i,j}$ years to hatch, and the hatched gremlin’s type is $g_{i,j}$. Ask: up to which generation is the gremlin that is currently the farthest from the ancestor, ignoring eggs that have not hatched yet. Assume the ancestor is generation $0$, its children are generation $1$, grandchildren are generation $2$, and so on.

The first line: $n,t$. Then follow $3n$ lines, grouped by three lines per type. The first line of each group: $k_i,y_i$. The second line of each group: $g_{i,1},\ldots,g_{i,k_i}$. The third line of each group: $h_{i,1},\ldots,h_{i,k_i}$.

One line with one integer, representing the largest generation number among gremlins that currently exist.

**[Sample #1 Explanation]** $10$ years after the accident, the initial gremlin (generation $0$) laid one egg and then died. $15$ years after the accident, the egg hatched into a new gremlin (generation $1$). $25$ years after the accident, the generation $1$ gremlin laid one egg and then died. $30$ years after the accident, the egg hatched into a new gremlin (generation $2$). $40$ years after the accident, the generation $2$ gremlin laid one egg and then died. $42$ years after the accident, this egg had still not hatched, so it is not counted. **[Constraints]** $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$。 The score of this problem follows the original COCI settings, with a full score of $130$. Translated by ChatGPT 5