New Year Festival

The ICPC (Incredibly Colossal and Particularly Comfortable) Theater holds several traditional events to celebrate the New Year.

Each event has a fixed duration that cannot be changed. You choose the start time of each event freely, but no two events may overlap. An event may start at the moment another event ends.

The start time of an event affects its cost. The cost of an event is a continuous piecewise linear function (a polygonal line) of its start time. Different events may have different cost functions.

Schedule all the events so that the total cost is minimized.

The input consists of a single test case in the following format.

$n$

$\text{Description}_1$

$\vdots$

$\text{Description}_n$

The first line contains $n$, the number of events, where $2 ≤ n ≤ 11$.

The description of the $i$-th event has the following format.

$m$ $l$

$x_1$ $y_1$

$\vdots$

$x_m$ $y_m$

The integer $m$ is the number of vertices of the cost function, and $l$ is the duration of the event. Here $1 ≤ m ≤ 60$ and $1 ≤ l ≤ 10^8$.

Each of the next $m$ lines gives a vertex $(x_j, y_j)$ of the cost function, where $0 ≤ x_1 < \cdots < x_m ≤ 10^8$ and $0 ≤ y_j ≤ 10^8$. For each $1 ≤ j < m$, the slope $(y_{j+1} - y_j)/(x_{j+1} - x_j)$ is an integer.

The start time $t$ of the event must satisfy $x_1 ≤ t ≤ x_m$. For $j$ with $x_j ≤ t ≤ x_{j+1}$, the cost of the event is $y_j + (t - x_j) \times (y_{j+1} - y_j)/(x_{j+1} - x_j)$.

The total number of vertices over all cost functions is at most $60$.

Output the minimum possible total cost in a single line.

It is guaranteed that at least one schedule without overlaps exists. The answer is always an integer.

For Sample Input 1, the (start time, end time) pairs $(330, 380)$, $(380, 500)$, and $(170, 330)$ for events 1, 2, and 3 give the minimum total cost without overlaps. The cost of event 1 is $2500 + (330 - 300) \times \frac{0 - 2500}{350 - 300} = 1000$. The costs of events 2 and 3 are 0 and 460.

For Sample Input 2, the minimum cost is reached with the pairs $(384, 544)$, $(104, 384)$, $(544, 704)$, and $(720, 960)$ for the four events.

Figure K.1. Cost functions in Sample Input 1 and a sample schedule

Figure K.2. Cost functions in Sample Input 2 and a sample schedule

In Figures K.1 and K.2, the polylines in the top figure are cost functions, and the rectangles in the bottom figure show event durations in a schedule with minimum total cost.