새해 축제

ICPC(Incredibly Colossal and Particularly Comfortable) 극장에서 새해를 축하하는 전통 행사를 여러 개 연다.

각 행사의 길이는 정해져 있어서 바꿀 수 없다. 행사의 시작 시각은 자유롭게 정할 수 있지만, 두 행사가 겹치면 안 된다. 한 행사가 끝나는 순간 다른 행사를 바로 시작해도 된다.

행사의 비용은 시작 시각에 따라 달라진다. 행사의 비용은 시작 시각에 대한 연속인 구간별 일차 함수(꺾은선 함수)로 주어지며, 행사마다 비용 함수가 다를 수 있다.

전체 비용이 최소가 되도록 모든 행사의 일정을 정하라.

입력은 다음 형식으로 주어지는 테스트 케이스 하나이다.

$n$

$\text{Description}_1$

$\vdots$

$\text{Description}_n$

첫 줄에는 행사의 개수 $n$이 주어진다. 단, $2 ≤ n ≤ 11$이다.

$i$번째 행사의 설명은 다음 형식이다.

$m$ $l$

$x_1$ $y_1$

$\vdots$

$x_m$ $y_m$

$m$은 비용 함수의 꼭짓점 개수이고, $l$은 행사의 길이이다. 여기서 $1 ≤ m ≤ 60$, $1 ≤ l ≤ 10^8$이다.

이어지는 $m$개의 줄은 비용 함수의 꼭짓점 $(x_j, y_j)$를 나타낸다. $0 ≤ x_1 < \cdots < x_m ≤ 10^8$, $0 ≤ y_j ≤ 10^8$이다. 모든 $1 ≤ j < m$에 대해 기울기 $(y_{j+1} - y_j)/(x_{j+1} - x_j)$는 정수이다.

행사의 시작 시각 $t$는 $x_1 ≤ t ≤ x_m$을 만족해야 한다. $x_j ≤ t ≤ x_{j+1}$인 $j$에 대해 행사의 비용은 $y_j + (t - x_j) \times (y_{j+1} - y_j)/(x_{j+1} - x_j)$이다.

모든 비용 함수의 꼭짓점 개수의 합은 $60$ 이하이다.

겹치지 않는 일정 중 전체 비용의 최솟값을 한 줄에 출력한다.

겹치지 않는 일정이 최소 하나는 존재함이 보장된다. 답은 항상 정수이다.

샘플 입력 1에서 행사 1, 2, 3의 (시작 시각, 종료 시각) 쌍을 각각 $(330, 380)$, $(380, 500)$, $(170, 330)$으로 정하면 겹침 없이 전체 비용이 최소가 된다. 행사 1의 비용은 $2500 + (330 - 300) \times \frac{0 - 2500}{350 - 300} = 1000$이다. 행사 2와 3의 비용은 각각 0과 460이다.

샘플 입력 2의 최소 비용은 네 행사를 각각 $(384, 544)$, $(104, 384)$, $(544, 704)$, $(720, 960)$으로 배치할 때 나온다.

그림 K.1. 샘플 입력 1의 비용 함수와 일정 예시

그림 K.2. 샘플 입력 2의 비용 함수와 일정 예시

그림 K.1과 K.2에서 위쪽 그림의 꺾은선은 비용 함수이고, 아래쪽 그림의 직사각형은 전체 비용이 최소인 일정에서 각 행사의 기간을 나타낸다.