Oppgavebeskrivelse

Ved en bestemt elv er det populært med en litt farlig lek som går ut på å hoppe fra stein til stein fra den ene bredden for å nå den motsatte bredden.

Figur $4\text{-}1$: Eksempel på steinposisjoner (Japanske etiketter i figuren: 反対側の岸 = Motsatt bredd, 川 = Elv, 始める岸 = Startbredd, 列 = Kolonne, 行 = Rad)

Som vist i Figur $4\text{-}1$ betrakter vi nå steinene som plassert på rutene i et rutenett. Antallet rader er $n$. I Figur $4\text{-}1$ er $n = 5$.

I denne leken starter man fra den ene bredden og krysser over til den motsatte bredden ved å gjøre vanlige hopp eller høyst $m$ hopp som hopper over én rad. Et vanlig hopp er å hoppe til bredden eller en av steinene på raden som ligger $1$ rad foran den nåværende raden, og et hopp som hopper over én rad er å hoppe til bredden eller en av steinene på raden som ligger $2$ rader foran den nåværende raden. Her er raden som ligger $1$ rad foran startbredden rad $1$, raden som ligger $2$ rader foran er rad $2$, og både raden som ligger $2$ rader foran rad $n-1$ og raden som ligger $1$ rad foran rad $n$ er den motsatte bredden.

For å gjennomføre denne leken så trygt som mulig bestemte vi oss for å se på faregraden til et hopp. Hver stein har en fast glatthet. Når man hopper fra én stein til en annen stein, enten det er et vanlig hopp eller et hopp som hopper over én rad, defineres faregraden til hoppet som:

(glattheten til den nåværende steinen $+$ glattheten til målsteinen) $\times$ (horisontal bevegelsesavstand)

Her er den horisontale bevegelsesavstanden differansen mellom kolonnenumrene. I tillegg er faregraden til et hopp fra en bredd til en stein, eller fra en stein til en bredd, lik $0$.

Gitt $n, m$ samt posisjonen og glattheten til hver stein som inndata, skriv et program for å finne den minste mulige totale faregraden for hoppene når man når den motsatte bredden. For de gitte inndataene er det garantert at det alltid er mulig å nå den motsatte bredden, og at ingen rute inneholder $2$ eller flere steiner.

Inndata

På den $1$. linjen står det $2$ heltall $n, m$ atskilt med et mellomrom. Disse representerer henholdsvis antallet rader og det tillatte antallet hopp som hopper over én rad. $n, m$ oppfyller henholdsvis $2 \le n \le 150$ og $0 \le m \le \frac{(n+1)}{2}$.

På de følgende $n$ linjene står det informasjon om steinene på hver rad. På den $i+1$. linjen ($1 \le i \le n$) står det $1$ heltall $k_{i}$ ($0 \le k_{i} \le 10$) etterfulgt av $2 \times k_{i}$ heltall atskilt med mellomrom. Disse representerer informasjonen om steinene på den $i$. raden telt fra startbredden.

$k_{i}$ representerer antallet steiner som finnes på den raden, og blant de følgende $2 \times k_{i}$ heltallene representerer det $2 \times j - 1$. ($1 \le j \le k_{i}$) heltallet $x_{i,j}$ kolonnenummeret til den $j$. steinen på den raden, og det $2 \times j$. heltallet $d_{i,j}$ representerer glattheten til den $j$. steinen på den raden. $x_{i,j}, d_{i,j}$ oppfyller henholdsvis $1 \le x_{i,j}, d_{i,j} \le 1000$.

Av testdataene oppfyller $20\%$ av poengene $n \le 6$, og ytterligere $20\%$ av poengene oppfyller $m = 0$.

Utdata

Utdataene består av $1$ linje som inneholder $1$ heltall som representerer den minste totale faregraden for hoppene når man når den motsatte bredden.

Eksempel

Anta i Figur $4\text{-}2$ at tallene som er skrevet på steinene representerer glattheten til hver stein. Når man krysser steinene i den rekkefølgen pilene viser, er faregradene til de respektive hoppene i rekkefølge $0$, $(2 + 2) \times 1 = 4$, $(2 + 1) \times 1 = 3$, $(1 + 4) \times 2 = 10$, $0$, og summen er $17$. I dette tilfellet er den totale faregraden for hoppene minimert.

Dette eksempelet tilsvarer Eksempel $1$.

Figur $4\text{-}2$: Eksempel på en rute

Eksempel på inndata og utdata

Inndata og utdata som tilsvarer eksempelet ovenfor er vist i Eksempel $1$.

Eksempelinndata 1

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

Eksempelutdata 1

17

Eksempelinndata 2

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

Eksempelutdata 2

40