題目描述

喺某條河度，興緊一種有少少危險嘅遊戲：由一邊河岸出發，逐舊石頭跳過去，最後去到對面岸。

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