ICPC（Incredibly Colossal and Particularly Comfortable）剧院正在举办一系列传统活动来庆祝新年！

每个活动都有其固定的持续时间。只要没有两个活动重叠，活动的开始时间就是灵活的。一个活动可以在另一个活动结束后立即开始。

活动的开始时间会影响成本。活动的成本是其开始时间的连续分段线性函数（折线函数）。不同的活动可能有不同的成本函数。

请你安排所有活动，使得总成本最小。

输入格式

输入包含单个测试用例，格式如下：

$n$ $Description_1$ $\vdots$ $Description_n$

第一行包含一个整数 $n$，表示活动的数量。满足 $2 \le n \le 11$。接下来是各活动的描述。第 $i$ 个活动的描述 $Description_i$ ($1 \le i \le n$) 格式如下：

$m \ l$ $x_1 \ y_1$ $\vdots$ $x_m \ y_m$

第一行中的整数 $m$ 是该活动成本函数的顶点数。同一行中的整数 $l$ 是该活动的持续时间。满足 $1 \le m \le 60$ 且 $1 \le l \le 10^8$。

接下来的 $m$ 行描述了成本函数。这 $m$ 行中的第 $j$ 行包含两个整数 $x_j$ 和 $y_j$，指定了成本函数的第 $j$ 个顶点。满足 $0 \le x_1 < \dots < x_m \le 10^8$ 且 $0 \le y_j \le 10^8$。此外，对于任何 $1 \le j < m$，$(y_{j+1} - y_j) / (x_{j+1} - x_j)$ 均为整数。

活动的开始时间 $t$ 必须满足 $x_1 \le t \le x_m$。对于满足 $x_j \le t \le x_{j+1}$ 的 $j$ ($1 \le j < m$)，活动的成本由 $y_j + (t - x_j) \times (y_{j+1} - y_j) / (x_{j+1} - x_j)$ 给出。

所有成本函数的顶点总数不超过 60。

输出格式

输出一行，表示所有活动的最小总成本。

题目保证至少存在一种没有重叠的合法调度方案。可以证明答案是一个整数。

样例

样例输入 1

3
3 50
300 2500
350 0
400 3000
2 120
380 0
400 2400
4 160
0 800
400 0
450 100
950 4600

样例输出 1

1460

样例输入 2

4
2 160
384 0
1000 2464
3 280
0 2646
441 0
1000 2795
1 160
544 0
2 240
720 0
1220 2000

样例输出 2

2022

说明

对于样例 1，将三个活动的（开始时间，结束时间）对分别设为 $(330, 380)$、$(380, 500)$ 和 $(170, 330)$，可以在没有活动重叠的情况下实现最小总成本。活动 1 的成本为 $2500 + (330 - 300) \times (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 中，顶部图形中的折线表示成本函数，底部图形中的矩形表示实现最小总成本的调度中各活动的持续时间。