COCI 2009/2010, Contest #6

Task GREMLINI

Gremlins are small, funny, fuzzy creatures. In times long gone they used to cause quite a ruckus, but now most of them live decent, honest family lives.

There are N different types of gremlins, coded with numbers 1 to N for your convenience. Legend has it that T years ago a laboratory accident occurred causing N gremlins, one of each type to be born.

As you all know, in order for gremlins to reproduce, no mating rituals are required. Just add a dash of watter and you instantly get a few new cocoons.

Gremlins of type i need exactly Y_i years to mature and spawn K_i cocoons. For each cocoon you know how much years does it take to hatch, and which gremlin type is contained within. The original gremlin unfortunately dies while producing cocoons.

Now, T years after the original accident. Scientist wonder what is the longest ancestral chain whose genome is currently represented. They are only interested in ancestors of hatched gremlins, not those still cocooned. You are safe to assume that all gremlins that were supposed to hatch this year did so.

Input

The first line of input contains two integers N and T (1 ≤ N ≤ 100, 1 ≤ T ≤ 10¹⁵), the number of gremlin types and the number of years after the original accident.

The next 3N lines contain gremlin type descriptions, three lines per type:

• The first line contains integers K_i and Y_i (1 ≤ K_i ≤ 1000, 1 ≤ Y_i ≤ 1000), the number of cocoons formed when this gremlin type spawns and number of years this gremlin type needs to reach maturity.
• The second line contains K_i integers between 1 and N inclusive, the types of gremlins hatched from cocoons formed by this gremlin type.
• The third line contains K_i integers between 1 and 1000, representing hatching time for each cocoon, in years.

Output

The first and only line of output should contain the length of the currently longest ancestral chain.

Sample Tests

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

Explanation of Sample 2

The original gremlin hatched in the accident after 10 years spawns a single cocoon and dies.

15 years after the accident, a new gremlin hatches from the cocoon. His ancestral chain contains one gremlin. 25 years after the accident this gremlin spawns a new cocoon and dies.

30 years after the accident, a new gremlin hatches from the cocoon. His ancestral chain contains two gremlins. 40 years after the accident this gremlin spawns a new cocoon and dies.

42 years after the accident, the current cocoon is not yet hatched, so the longest ancestral chain ever recorded is two gremlins in length.

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 1.00s
Memory Limit: 32M
Added: Aug 13, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)