COCI '09 Contest 6 #6 Gremlini

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem type

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 water 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 many years it takes 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 Specification

The first line of input contains two integers N and T (1 \le N \le 100, 1 \le T \le 10^{15}), 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 \le K_i \le 1\,000, 1 \le Y_i \le 1\,000), 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 1\,000, representing hatching time for each cocoon, in years.

Output Specification

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

Sample Input 1

1 42
1 10
1
5

Sample Output 1

2

Sample Input 2

2 42
1 10
1
5
1 5
1
5

Sample Output 2

3

Sample Input 3

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

Sample Output 3

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.


Comments

There are no comments at the moment.