题目描述

在某条河上，流行着一种稍微有些危险的游戏：从一侧河岸出发，依次跳到石头上，最终到达对岸。

图 $4\text{-}1$：石头位置示例（图中日文标注：反対側の岸 = 对岸，川 = 河，始める岸 = 起始岸，列 = 列，行 = 行）

现在，如图 $4\text{-}1$ 所示，我们认为石头位于方格网格上。行数为 $n$。在图 $4\text{-}1$ 中，$n = 5$。

在这个游戏中，从一侧河岸出发，通过进行普通跳跃或最多 $m$ 次跨一行跳跃来到达对岸。所谓普通跳跃，是指跳到当前所在行前方第 $1$ 行的河岸或某块石头上；所谓跨一行跳跃，是指跳到当前所在行前方第 $2$ 行的河岸或某块石头上。这里，起始岸前方第 $1$ 行是第 $1$ 行，前方第 $2$ 行是第 $2$ 行，而第 $n-1$ 行前方第 $2$ 行以及第 $n$ 行前方第 $1$ 行是对岸。

现在，为了尽可能安全地完成这个游戏，我们决定考虑跳跃的危险度。每块石头都有固定的湿滑度。从一块石头跳到另一块石头时，无论是普通跳跃还是跨一行跳跃，跳跃的危险度定义为：

（当前所在石头的湿滑度 $+$ 目标石头的湿滑度）$\times$（横向移动距离）

其中，横向移动距离是指列号之差。另外，从河岸跳到石头上，或者从石头跳到河岸上的跳跃危险度为 $0$。

给定 $n, m$ 以及每块石头的位置和湿滑度作为输入，请编写程序求出到达对岸时跳跃危险度总和的最小值。对于给定的输入数据，保证一定能够到达对岸，且同一个方格内不会存在 $2$ 块或以上的石头。

输入格式

第 $1$ 行包含以空格分隔的 $2$ 个整数 $n, m$。它们分别表示行数以及允许进行跨一行跳跃的次数。$n, m$ 分别满足 $2 \le n \le 150$，$0 \le m \le \frac{(n+1)}{2}$。

接下来的 $n$ 行包含每一行中石头的信息。第 $i+1$ 行（$1 \le i \le n$）包含 $1$ 个整数 $k_{i}$（$0 \le k_{i} \le 10$）以及随后的 $2 \times k_{i}$ 个整数，以空格分隔。这些数表示从起始岸数起第 $i$ 行中石头的信息。

$k_{i}$ 表示该行中存在的石头数量。对于随后的 $2 \times k_{i}$ 个整数，第 $2 \times j - 1$ 个（$1 \le j \le k_{i}$）整数 $x_{i,j}$ 表示该行第 $j$ 块石头的列号，第 $2 \times j$ 个整数 $d_{i,j}$ 表示该行第 $j$ 块石头的湿滑度。$x_{i,j}, d_{i,j}$ 分别满足 $1 \le x_{i,j}, d_{i,j} \le 1000$。

在评测数据中，$20\%$ 的分数满足 $n \le 6$，另有 $20\%$ 的分数满足 $m = 0$。

输出格式

输出共 $1$ 行，包含 $1$ 个整数，表示到达对岸时跳跃危险度总和的最小值。

示例说明

在图 $4\text{-}2$ 中，设石头上所写的数字表示各块石头的湿滑度。当按照箭头所示的顺序渡过石头时，每次跳跃的危险度依次为 $0$、$(2 + 2) \times 1 = 4$、$(2 + 1) \times 1 = 3$、$(1 + 4) \times 2 = 10$、$0$，总和为 $17$。此时，跳跃危险度的总和达到最小。

此示例对应于样例 $1$。

图 $4\text{-}2$：路线示例

样例输入与输出

与上述示例对应的输入输出如样例 $1$ 所示。

样例输入 1

5 1
2 1 3 2 2
1 3 2
1 1 7
1 2 1
1 4 4

样例输出 1

17

样例输入 2

5 0
2 1 3 2 2
1 3 2
1 1 7
1 2 1
1 4 4

样例输出 2

40