Lýsing á verkefni

Við tiltekna á er vinsæll svolítið hættulegur leikur sem felst í því að hoppa af steini á stein frá öðrum bakkanum til að komast yfir á hinn bakkann.

Mynd $4\text{-}1$: Dæmi um staðsetningu steina (Japanskar merkingar á myndinni: 反対側の岸 = Hinn bakkinn, 川 = Á, 始める岸 = Upphafsbakki, 列 = Dálkur, 行 = Röð)

Eins og sýnt er á Mynd $4\text{-}1$ lítum við svo á að steinarnir séu á reitum í hnitakerfi. Fjöldi raða er $n$. Á Mynd $4\text{-}1$ er $n = 5$.

Í þessum leik byrjar maður á öðrum bakkanum og fer yfir á hinn bakkann með því að taka venjuleg stökk eða í mesta lagi $m$ stökk sem sleppa einni röð. Venjulegt stökk felst í því að stökkva á bakkann eða einn af steinunum í röðinni sem er $1$ röð fyrir framan núverandi röð, og stökk sem sleppir einni röð felst í því að stökkva á bakkann eða einn af steinunum í röðinni sem er $2$ röðum fyrir framan núverandi röð. Hér er röðin sem er $1$ röð fyrir framan upphafsbakkann röð $1$, röðin sem er $2$ röðum fyrir framan er röð $2$, og bæði röðin sem er $2$ röðum fyrir framan röð $n-1$ og röðin sem er $1$ röð fyrir framan röð $n$ eru hinn bakkinn.

Til að leysa þennan leik af eins miklu öryggi og hægt er ákváðum við að taka tillit til hættustigs stökks. Hver steinn hefur fasta hálku. Þegar stokkið er af einum steini yfir á annan stein, hvort sem það er venjulegt stökk eða stökk sem sleppir einni röð, er hættustig stökksins skilgreint sem:

(hálka núverandi steins $+$ hálka áfangasteins) $\times$ (lárétt fjarlægð)

Hér er lárétt fjarlægð mismunurinn á dálkanúmerunum. Auk þess er hættustig stökks af bakka á stein, eða af steini á bakka, jafnt og $0$.

Gefið $n, m$ ásamt staðsetningu og hálku hvers steins sem inntak, skrifið forrit til að finna minnstu mögulegu heildarsummu hættustiga stökkvanna þegar komið er yfir á hinn bakkann. Fyrir gefin inntaksgögn er tryggt að alltaf sé hægt að komast yfir á hinn bakkann og að enginn reitur innihaldi $2$ eða fleiri steina.

Inntak

Á $1$. línu eru skrifaðar $2$ heiltölur $n, m$ aðskildar með bili. Þær tákna annars vegar fjölda raða og hins vegar leyfilegan fjölda stökka sem sleppa einni röð. $n, m$ uppfylla $2 \le n \le 150$ og $0 \le m \le \frac{(n+1)}{2}$, í sömu röð.

Á næstu $n$ línum eru skrifaðar upplýsingar um steinana í hverri röð. Á $i+1$-tu línu ($1 \le i \le n$) er skrifuð $1$ heiltala $k_{i}$ ($0 \le k_{i} \le 10$) og á eftir henni koma $2 \times k_{i}$ heiltölur aðskildar með bilum. Þær tákna upplýsingar um steinana í $i$-tu röð talið frá upphafsbakkanum.

$k_{i}$ táknar fjölda steina sem eru í þeirri röð, og af næstu $2 \times k_{i}$ heiltölum táknar $2 \times j - 1$-ta ($1 \le j \le k_{i}$) heiltalan $x_{i,j}$ dálkanúmer $j$-ta steinsins í þeirri röð, og $2 \times j$-ta heiltalan $d_{i,j}$ táknar hálku $j$-ta steinsins í þeirri röð. $x_{i,j}, d_{i,j}$ uppfylla $1 \le x_{i,j}, d_{i,j} \le 1000$.

Af prófunargögnunum uppfyllir $20\%$ stiganna $n \le 6$, og önnur $20\%$ stiganna uppfylla $m = 0$.

Úttak

Úttakið samanstendur af $1$ línu sem inniheldur $1$ heiltölu sem táknar lágmarks heildarsummu hættustiga stökkvanna þegar komið er yfir á hinn bakkann.

Dæmi

Á Mynd $4\text{-}2$ skulum við gera ráð fyrir að tölurnar sem skrifaðar eru á steinana tákni hálku hvers steins. Þegar farið er yfir steinana í þeirri röð sem örvarnar sýna eru hættustig viðkomandi stökka í röð $0$, $(2 + 2) \times 1 = 4$, $(2 + 1) \times 1 = 3$, $(1 + 4) \times 2 = 10$, $0$, og summan er $17$. Í þessu tilfelli er heildarsumma hættustiga stökkvanna í lágmarki.

Þetta dæmi samsvarar Sýnidæmi $1$.

Mynd $4\text{-}2$: Dæmi um leið

Sýnidæmi um inntak og úttak

Inntakið og úttakið sem samsvara dæminu hér að ofan eru sýnd í Sýnidæmi $1$.

Sýnidæmi um inntak 1

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

Sýnidæmi um úttak 1

17

Sýnidæmi um inntak 2

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

Sýnidæmi um úttak 2

40