Virus Bomb

A chemist has built an atomic virus bomb. It works like this.

The virus has $N$ different forms. Every second, a virus of one form transforms into one or more viruses of the same form or of other forms. Each form also produces a fixed number of tritium atoms during the second the transformation takes. When the total number of atoms produced so far reaches the critical limit $L$, they explode as a hydrogen bomb.

We want to know how long it takes from the moment a patient is infected until the bomb goes off.

Take a virus with a single form. Every second it transforms into two viruses of the same form and produces one tritium atom, and $L = 15$. After one second there are two viruses and one atom. After two seconds there are four viruses and three atoms. After three seconds there are eight viruses and seven atoms. After four seconds the bomb goes off.

Now take a virus with two forms A and B, with $L = 500$. Every second a virus of form A transforms into three viruses of form A and one virus of form B, and produces one tritium atom. A virus of form B transforms into two viruses of form B and produces one hundred tritium atoms. Starting from one virus of form A, after one second there are 3 A, 1 B and 1 atom. After two seconds there are 9 A, 5 B and 104 atoms. After three seconds there are 27 A, 19 B and 613 atoms. The answer is three seconds.

The first line contains the number of test cases $T$ ($1 \le T \le 100$).

The first line of each test case contains $N$ and $L$ ($1 \le N \le 20$, $1 \le L \le 10^9$).

The next $N$ lines describe the forms, one line per form. Each line holds $N+1$ non-negative integers smaller than $1000$. The first $N$ tell how many viruses of each form this form transforms into. The last one tells how many tritium atoms it produces while transforming.

Print one line for each test case. The patient starts infected with one virus of the first form. Atoms are never removed, so the total only grows. Print the number of seconds until that total first reaches $L$. If the bomb never goes off, print lucky. The answer can exceed the range of a 32-bit integer.