27426번 - New Year Festival 다국어

The ICPC (Incredibly Colossal and Particularly Comfortable) Theater is giving a number of traditional events to celebrate the New Year!

Each of the events has its own unalterable duration. Start times of the events are flexible as long as no two events overlap. An event may start immediately after another event ends.

Start times of the events influence the costs. The cost of an event is given by a continuous piecewise linear function (a polygonal line function) of its start time. Different events may have different cost functions.

You are asked to schedule all the events minimizing the total cost.

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

$n$

$\text{Description}_1$

$\vdots$

$\text{Description}_n$

The first line contains an integer $n$, representing the number of events. $2 ≤ n ≤ 11$ holds. The descriptions of the events follow. The description of the $i$-th event, $\text{Description}_i$ ($1 ≤ i ≤ n$), has the following format.

$m$ $l$

$x_1$ $y_1$

$\vdots$

$x_m$ $y_m$

The integer $m$ in the first line is the number of vertices of the cost function of the event. The integer $l$ in the same line is the duration of the event. $1 ≤ m ≤ 60$ and $1 ≤ l ≤ 10^8$ hold.

The following $m$ lines describe the cost function. The $j$-th line of the $m$ lines consists of the two integers $x_j$ and $y_j$ specifying the $j$-th vertex of the cost function. $0 ≤ x_1 < \cdots < x_m ≤ 10^8$ and $0 ≤ y_j ≤ 10^8$ hold. In addition, $(y_{j+1} - y_j)/(x_{j+1} - x_j)$ is an integer for any $1 ≤ j < m$.

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

The total number of the vertices of all the cost functions is not greater than $60$.

Output the minimum possible total cost of the events in a line.

It is guaranteed that there is at least one possible schedule containing no overlap. It can be proved that the answer is an integer.

For Sample Input 1, making the (start time, end time) pairs of the three events to be $(330, 380)$, $(380, 500)$, and $(170, 330)$, respectively, achieves the minimum total cost without event overlaps. The cost of the event $1$ is $2500 + (330 - 300) \times (0 - 2500)/(350 - 300) = 1000$. Similarly, the costs of the events $2$ and $3$ are $0$ and $460$, respectively.

For Sample Input 2, the minimum cost is achieved by $(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, polylines in the top figure represent cost functions, and rectangles in the bottom figure represent event durations of a schedule achieving the minimum total cost.