GREMLINS - Gremlins

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, Ki 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 Yi 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 ≤ 1015), 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 Ki and Yi (1 ≤ Yi ≤ 1000, 1 ≤ Ki ≤ 1000).

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

The third line contain Ki 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

Added by:Luka Kalinovcic
Date:2009-08-06
Time limit:0.709s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS OBJC PERL6 SQLITE VB.NET
Resource:own problem

hide comments
2021-08-27 12:45:05
:)
2017-10-26 18:58:38 Sigma Kappa
Accepted with the help of @Blue.Mary and @Adrian.Kuegel. Thank you both!
2017-10-26 03:06:15 [Rampage] Blue.Mary
Yes, this is a common trick that can be used in many problems. (Optimize log n binary search the answer * log n calculate the answer => only one log n).
2017-10-26 00:33:10 Sigma Kappa
@Blue.Mary, thanks for letting me know your complexity. That means I have to get rid of one extra log(T), which I used to decide the largest power of the matrix such that its smallest entry is still <= T.

Last edit: 2017-10-26 00:37:04
2017-10-24 03:21:12 [Rampage] Blue.Mary
My algo is O(log(T) * n^3), easily passed.
2017-10-24 00:50:30 Sigma Kappa
My algo is O(log^2(T)*n^3). Getting TLE. Should we go for lesser complexity, then?

Last edit: 2017-10-24 01:55:33
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.