題目描述

在某條河上，流行著一種稍微有些危險的遊戲：從一側河岸出發，依序跳到石頭上，最終到達對岸。

圖 $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