Grade Consolidation

The school Yeongseon attends, sys School, lost part of its classrooms to a natural disaster. Only $m$ classrooms are still usable. The school has grades 1 through $n$, and grade $i$ has $a_i$ classes.

Because classrooms are short, all classes of one grade go into a single classroom. When that is still not enough, all classes of two adjacent grades, whose education levels are the closest, go into one classroom. Grade 2, for example, can share a classroom with grade 1 or with grade 3.

Classes in the same grade take common subjects, so they sit together without trouble. Between different grades, even one year apart, some pairs of classes cannot attend together because of the humanities and science split or different elective subjects. When two adjacent grades share a classroom, one class out of each such pair is dropped and receives no classroom.

For fairness, two grades may share one classroom, but no grade ever uses two classrooms. Each grade therefore takes a classroom alone, shares one classroom with one adjacent grade, or receives no classroom at all. No classroom holds three or more grades.

Assign the $m$ classrooms this way so that the number of classes that receive a classroom is as large as possible. Print that maximum.

The first line has the number of grades $n$ and the number of usable classrooms $m$. ($1 \le n \le 50$, $\lfloor n/2 \rfloor \le m \le n$)

The grades follow in order from grade 1 to grade $n$. Each grade starts with a line holding its class count $a_i$. ($1 \le a_i \le 100$)

For a grade with $i < n$, that line is followed by $a_i$ lines. The $j$th of them describes class $j$ of grade $i$: the count $b$ of classes of grade $i+1$ that cannot attend with it, then those $b$ class numbers. ($0 \le b \le a_{i+1}$, the numbers are between 1 and $a_{i+1}$ and are distinct)

The highest grade, grade $n$, is given as its class count $a_n$ only.

Print on the first line the maximum number of classes that receive a classroom under the best assignment.