Ancestral Generation Chain

Consider a population of little creatures of n distinct types, numbered from (1) to (n). Exactly (t) years ago, an accident produced one newborn of each type (they are considered as the 1^st generation). For each type (i), a creature needs (y_i) years to mature. Once mature, it instantly produces (k_i) eggs and then dies. The eggs are numbered from (1) to (k_i). The (j)-th egg of a creature of type (i) takes (h_{i,j}) years to hatch and becomes a creature of type (g_{i,j}).

A creature born from an egg is considered to be one generation later than its parent (i.e. the ancestors are generation 1, their children generation 2, and so on). Given that only eggs which have hatched are considered, determine the maximum generation number that appears by time (t) (years).

Formally, if a creature of type (i) is born at time (T), it produces an egg (number (j)) which hatches (producing a new creature) at time (T + y_i + h_{i,j}). Only hatching events with time (\le t) are valid.

inputFormat

The input consists of multiple lines. The first line contains two integers (n) and (t) -- the number of types and the total time elapsed, respectively.

The second line contains (n) integers: (y_1, y_2, \dots, y_n), where (y_i) is the maturation time for a creature of type (i).

The third line contains (n) integers: (k_1, k_2, \dots, k_n), where (k_i) is the number of eggs a mature creature of type (i) produces.

Then, for each type (i) from (1) to (n), if (k_i \gt 0), there is a line containing (2\times k_i) integers: (h_{i,1}, g_{i,1}, h_{i,2}, g_{i,2}, \dots, h_{i,k_i}, g_{i,k_i}). If (k_i = 0), the corresponding line will be empty or omitted.

outputFormat

Output a single integer representing the maximum generation number reached by time (t) (including the initial generation).

sample

2 10
1 2
1 1
3 2
4 1

3