Tehtävänanto

Eräällä joella on suosittua hieman vaarallinen leikki, jossa hypitään kiveltä kivelle toiselta rannalta vastakkaiselle rannalle.

Kuva $4\text{-}1$: Esimerkki kivien sijainneista (Kuvan japaninkieliset tekstit: 反対側の岸 = Vastakkainen ranta, 川 = Joki, 始める岸 = Lähtöranta, 列 = Sarake, 行 = Rivi)

Kuten Kuvassa $4\text{-}1$ on esitetty, ajattelemme kivien sijaitsevan ruudukon ruuduissa. Rivien lukumäärä on $n$. Kuvassa $4\text{-}1$ on $n = 5$.

Tässä leikissä lähdetään toiselta rannalta ja ylitetään joki vastakkaiselle rannalle tekemällä tavallisia hyppyjä tai enintään $m$ yhden rivin yli hyppäävää hyppyä. Tavallinen hyppy tarkoittaa hyppäämistä rannalle tai jollekin kivelle rivillä, joka on $1$ rivin nykyisen rivin edellä, ja yhden rivin yli hyppäävä hyppy tarkoittaa hyppäämistä rannalle tai jollekin kivelle rivillä, joka on $2$ riviä nykyisen rivin edellä. Tässä lähtörannasta $1$ rivin edellä oleva rivi on rivi $1$, $2$ riviä edellä oleva rivi on rivi $2$, ja sekä rivistä $n-1$ nähden $2$ riviä edellä oleva rivi että rivistä $n$ nähden $1$ rivin edellä oleva rivi ovat vastakkainen ranta.

Jotta tämä leikki voitaisiin suorittaa mahdollisimman turvallisesti, päätimme tarkastella hypyn vaarallisuutta. Jokaisella kivellä on kiinteä liukkaus. Kun hypätään kiveltä toiselle kivelle – olipa kyseessä tavallinen hyppy tai yhden rivin yli hyppäävä hyppy – hypyn vaarallisuus määritellään seuraavasti:

(nykyisen kiven liukkaus $+$ kohdekiven liukkaus) $\times$ (vaakasuuntainen siirtymämatka)

Tässä vaakasuuntainen siirtymämatka on sarakkeiden numeroiden erotus. Lisäksi rannalta kivelle tai kiveltä rannalle suuntautuvan hypyn vaarallisuus on $0$.

Kun syötteenä annetaan $n, m$ sekä kunkin kiven sijainti ja liukkaus, kirjoita ohjelma, joka etsii hyppyjen vaarallisuuksien pienimmän mahdollisen kokonaissumman vastakkaiselle rannalle päästäessä. Annetuilla syötetiedoilla on taattu, että vastakkaiselle rannalle on aina mahdollista päästä ja ettei missään ruudussa ole $2$ tai useampaa kiveä.

Syöte

Rivillä $1$ on $2$ välilyönnillä erotettua kokonaislukua $n, m$. Nämä ilmaisevat rivien lukumäärän ja yhden rivin yli hyppäävien hyppyjen sallitun enimmäismäärän. Luvut $n, m$ toteuttavat ehdot $2 \le n \le 150$ ja $0 \le m \le \frac{(n+1)}{2}$.

Seuraavilla $n$ rivillä on tiedot kunkin rivin kivistä. Rivillä $i+1$ ($1 \le i \le n$) on $1$ kokonaisluku $k_{i}$ ($0 \le k_{i} \le 10$) ja sen perässä $2 \times k_{i}$ välilyönnein erotettua kokonaislukua. Nämä ilmaisevat tiedot lähtörannasta laskien $i$:nnellä rivillä olevista kivistä.

$k_{i}$ ilmaisee kyseisellä rivillä olevien kivien lukumäärän, ja seuraavista $2 \times k_{i}$ kokonaisluvusta $2 \times j - 1$:s ($1 \le j \le k_{i}$) kokonaisluku $x_{i,j}$ ilmaisee kyseisen rivin $j$:nnen kiven sarakkeen numeron ja $2 \times j$:s kokonaisluku $d_{i,j}$ ilmaisee kyseisen rivin $j$:nnen kiven liukkauden. Luvut $x_{i,j}, d_{i,j}$ toteuttavat ehdon $1 \le x_{i,j}, d_{i,j} \le 1000$.

Testiaineistosta $20\%$ pisteistä toteuttaa ehdon $n \le 6$, ja toiset $20\%$ pisteistä toteuttaa ehdon $m = 0$.

Tuloste

Tuloste koostuu $1$ rivistä, jolla on $1$ kokonaisluku: hyppyjen vaarallisuuksien pienin mahdollinen kokonaissumma vastakkaiselle rannalle päästäessä.

Esimerkki

Oletetaan, että Kuvassa $4\text{-}2$ kiville kirjoitetut luvut kuvaavat kunkin kiven liukkautta. Kun kivet ylitetään nuolten osoittamassa järjestyksessä, vastaavien hyppyjen vaarallisuudet ovat järjestyksessä $0$, $(2 + 2) \times 1 = 4$, $(2 + 1) \times 1 = 3$, $(1 + 4) \times 2 = 10$, $0$, ja niiden summa on $17$. Tässä tapauksessa hyppyjen vaarallisuuksien summa on pienin mahdollinen.

Tämä esimerkki vastaa Esimerkkiä $1$.

Kuva $4\text{-}2$: Esimerkki reitistä

Esimerkkisyöte ja -tuloste

Yllä olevaa esimerkkiä vastaavat syöte ja tuloste on esitetty Esimerkissä $1$.

Esimerkkisyöte 1

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

Esimerkkituloste 1

17

Esimerkkisyöte 2

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

Esimerkkituloste 2

40