Problembeskrivning

Vid en viss flod är en något farlig lek populär, där man hoppar från sten till sten från den ena stranden för att nå den motsatta stranden.

Figur $4\text{-}1$: Exempel på stenarnas positioner (Japanska etiketter i figuren: 反対側の岸 = Motsatta stranden, 川 = Flod, 始める岸 = Startstranden, 列 = Kolumn, 行 = Rad)

Som visas i Figur $4\text{-}1$ betraktar vi nu stenarna som placerade på rutorna i ett rutnät. Antalet rader är $n$. I Figur $4\text{-}1$ är $n = 5$.

I denna lek börjar man vid den ena stranden och tar sig över till den motsatta stranden genom att göra vanliga hopp eller högst $m$ hopp som hoppar över en rad. Ett vanligt hopp innebär att man hoppar till stranden eller en av stenarna på raden som ligger $1$ rad framför den nuvarande raden, och ett hopp som hoppar över en rad innebär att man hoppar till stranden eller en av stenarna på raden som ligger $2$ rader framför den nuvarande raden. Här är raden som ligger $1$ rad framför startstranden rad $1$, raden som ligger $2$ rader framför är rad $2$, och såväl raden som ligger $2$ rader framför rad $n-1$ som raden som ligger $1$ rad framför rad $n$ utgör den motsatta stranden.

För att genomföra denna lek så säkert som möjligt bestämde vi oss för att betrakta farlighetsgraden för ett hopp. Varje sten har en fast halhet. När man hoppar från en sten till en annan sten, oavsett om det är ett vanligt hopp eller ett hopp som hoppar över en rad, definieras hoppets farlighetsgrad som:

(den nuvarande stenens halhet $+$ målstenens halhet) $\times$ (horisontell förflyttningssträcka)

Här är den horisontella förflyttningssträckan skillnaden mellan kolumnnumren. Dessutom är farlighetsgraden för ett hopp från en strand till en sten, eller från en sten till en strand, lika med $0$.

Givet $n, m$ samt varje stens position och halhet som indata, skriv ett program för att hitta den minsta möjliga totala farlighetsgraden för hoppen när man når den motsatta stranden. För givna indata garanteras att det alltid är möjligt att nå den motsatta stranden, och att ingen ruta innehåller $2$ eller fler stenar.

Indata

På den $1$:a raden står $2$ heltal $n, m$ åtskilda av ett mellanslag. Dessa representerar antalet rader respektive det tillåtna antalet hopp som hoppar över en rad. $n, m$ uppfyller $2 \le n \le 150$ respektive $0 \le m \le \frac{(n+1)}{2}$.

På de följande $n$ raderna står information om stenarna på varje rad. På den $i+1$:a raden ($1 \le i \le n$) står $1$ heltal $k_{i}$ ($0 \le k_{i} \le 10$) följt av $2 \times k_{i}$ heltal åtskilda av mellanslag. Dessa representerar informationen om stenarna på den $i$:te raden räknat från startstranden.

$k_{i}$ representerar antalet stenar som finns på den raden, och bland de följande $2 \times k_{i}$ heltalen representerar det $2 \times j - 1$:a ($1 \le j \le k_{i}$) heltalet $x_{i,j}$ kolumnnumret för den $j$:te stenen på den raden, och det $2 \times j$:te heltalet $d_{i,j}$ representerar halheten för den $j$:te stenen på den raden. $x_{i,j}, d_{i,j}$ uppfyller $1 \le x_{i,j}, d_{i,j} \le 1000$.

Av testdata uppfyller $20\%$ av poängen $n \le 6$, och ytterligare $20\%$ av poängen uppfyller $m = 0$.

Utdata

Utdata består av $1$ rad som innehåller $1$ heltal vilket representerar den minsta totala farlighetsgraden för hoppen när man når den motsatta stranden.

Exempel

Antag i Figur $4\text{-}2$ att talen som står på stenarna representerar varje stens halhet. När man tar sig över stenarna i den ordning som pilarna visar är farlighetsgraderna för respektive hopp i ordning $0$, $(2 + 2) \times 1 = 4$, $(2 + 1) \times 1 = 3$, $(1 + 4) \times 2 = 10$, $0$, och summan blir $17$. I detta fall minimeras den totala farlighetsgraden för hoppen.

Detta exempel motsvarar Exempel $1$.

Figur $4\text{-}2$: Exempel på en väg

Exempel på indata och utdata

Indata och utdata som motsvarar exemplet ovan visas i Exempel $1$.

Exempelindata 1

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

Exempelutdata 1

17

Exempelindata 2

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

Exempelutdata 2

40