Problem Description

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.

Input Format

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}$.

Output Format

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

1 42
1 10
1
5

2

2 42
1 10
1
5
1 5
1
5

3

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

4

Hint

[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