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, scientists 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.

The first line of input contains two integers \(N\) and \(T\) (\(1 \le N \le 100\), \(1 \le T \le 10^{15}\)), number of gremlin types and number of years after the original accident.

The next \(3 \cdot N\) lines contain gremlin type descriptions, three lines per type:

• The first line contains integers \(K_i\) and \(Y_i\) (\(1 \le K_i \le 1000\), \(1 \le Y_i \le 1000\)), 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, 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.

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

Second sample description: The original gremlin hatches 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.

riseoj 작성

출처 COCI 2009/2010 Contest 6