Let ~x_D[i]~ be the number of years until the birth of the first type ~i~ gremlin with ~D~ ancestors. Since there is one of each type of gremlins born in the accident we can set ~x_0[i] = 0~, for each ~i~.

Examine one type ~i~ gremlin with ~D~ ancestors. After ~Y_i~ years he spawns one type ~j~ egg, that needs ~Z_{i,j}~ years to hatch. That egg has ~D+1~ ancestors. So we now know that ~x_{D+1}[j]~ is less than or equal to ~x_D[i] + Y_i + Z~. Obviously, finding the minimum of all such values for all gremlins that hatch type ~j~ eggs we obtain ~x_{D+1}[j]~. We can observe all types at once by using matrix algebra. We have:

$$\displaystyle A \otimes X_D = X_{D+1}$$

Where ~A~ is a rectangular matrix with ~i^\text{th}~ row and ~j^\text{th}~ column equal to ~Y_j + Z_{j,i}~ if type ~j~ gremlin hatches type ~i~ egg, or ~\infty~ if not. Matrices ~X_D~ and ~X_{D+1}~ are self explanatory, and ~\otimes~ marks min-plus matrix multiplication.

Matrix ~A~ can be raised to arbitrary power fast using binary exponentiation. After multiplying ~A~ to the power of ~D~ and performing min-plus with ~X_0~ we scan the obtained ~X_D~ matrix. If each number is larger than ~T~, there are no gremlins with ~D~ ancestors. Otherwise, there is at least one. Using binary search on ~D~ we find the largest possible ~D~.