Gremlins are small funny furry creatures. Once they were considered to be evil but that time has past and most gremlins live a decent family life now. There are N distinct types of gremlins.

Their origin is rather mysterious. Legend says that T years ago, N gremlins, one of each type, were born in a lab accident.

Their reproduction method is, however, well studied. No mating ritual is required for gremlins to multiply. All they need is a few drops of water and the magic happens.

Once a type i gremlin starts its reproduction process, K_i small furry balls are created. For each furry ball we know what is the type of gremlin that will hatch from the furry ball and how long will it take for that to happen. Unfortunately, the original gremlin dies in the process. A type i gremlin will start its reproduction process exactly Y_i years after it is born (ie. hatched from the furry ball).

Knowledge about the ancestors of a gremlin is passed on genetically, so each gremlin knows a list of his ancestors as soon as it is born.

Write a program that will find the length of the longest list of ancestors among all gremlins that ever lived (gremlins that still live are included, but unhatched furry balls are not), given the information about reproduction process and time elapsed since the lab accident that created initial gremlins, assuming all gremlins that were supposed to hatch this year have already hatched.

Input

The first line contains two integers N and T (1 ≤ N ≤ 100, 1 ≤ T ≤ 10¹⁵), the number of gremlin types and the number of year that has passed since the lab accident.

The next 3·N lines give reproduction details for each gremlin type.

The first line of i-th block contains two integers K_i and Y_i (1 ≤ Y_i ≤ 1000, 1 ≤ K_i ≤ 1000).

The second line contains K_i integers representing gremlin type for each furry ball.

The third line contain K_i integers between 1 and 1000 representing hatching time for each furry ball, in years.

Output

Output the length of the longest list of ancestors among all gremlins that ever lived in a single line.

Examples

Input:
1 42
1 10
1
5
Output:
2

Input:
2 42
1 10
1
5
1 5
1
5
Output:
3

Input:
3 8
4 5
1 2 3 2
1 2 1 3
1 1
3
1
2 1
1 2
2 1
Output:
4