Testo del problema

Presso un certo fiume è popolare un gioco un po' pericoloso che consiste nel saltare di pietra in pietra partendo da una riva per raggiungere la riva opposta.

Figura $4\text{-}1$: Esempio di posizioni delle pietre (Etichette giapponesi nella figura: 反対側の岸 = Riva opposta, 川 = Fiume, 始める岸 = Riva di partenza, 列 = Colonna, 行 = Riga)

Ora, come mostrato nella Figura $4\text{-}1$, consideriamo che le pietre si trovino sulle caselle di una griglia. Il numero di righe è $n$. Nella Figura $4\text{-}1$, $n = 5$.

In questo gioco, partendo da una riva, si attraversa fino alla riva opposta effettuando salti normali oppure al massimo $m$ salti che scavalcano una riga. Un salto normale consiste nel saltare sulla riva o su una delle pietre nella riga situata $1$ riga più avanti rispetto alla riga corrente, mentre un salto che scavalca una riga consiste nel saltare sulla riva o su una delle pietre nella riga situata $2$ righe più avanti rispetto alla riga corrente. Qui, la riga situata $1$ riga più avanti rispetto alla riva di partenza è la riga $1$, quella situata $2$ righe più avanti è la riga $2$, e sia la riga situata $2$ righe più avanti rispetto alla riga $n-1$ sia la riga situata $1$ riga più avanti rispetto alla riga $n$ rappresentano la riva opposta.

Ora, per portare a termine questo gioco nel modo più sicuro possibile, abbiamo deciso di considerare il livello di pericolo di un salto. Ogni pietra ha una scivolosità fissa. Quando si salta da una pietra a un'altra, sia con un salto normale sia con un salto che scavalca una riga, il livello di pericolo del salto è definito come:

(scivolosità della pietra corrente $+$ scivolosità della pietra di destinazione) $\times$ (distanza di spostamento orizzontale)

Qui, la distanza di spostamento orizzontale è la differenza tra i numeri di colonna. Inoltre, il livello di pericolo di un salto da una riva a una pietra, o da una pietra a una riva, è $0$.

Dati in ingresso $n, m$ e la posizione e la scivolosità di ciascuna pietra, scrivi un programma per trovare il minimo totale possibile del livello di pericolo dei salti per raggiungere la riva opposta. Per i dati di ingresso forniti, è garantito che è sempre possibile raggiungere la riva opposta e che nessuna casella contiene $2$ o più pietre.

Dati di ingresso

Sulla $1$-a riga sono scritti $2$ interi $n, m$ separati da uno spazio. Essi rappresentano rispettivamente il numero di righe e il numero consentito di salti che scavalcano una riga. $n, m$ soddisfano rispettivamente $2 \le n \le 150$ e $0 \le m \le \frac{(n+1)}{2}$.

Sulle successive $n$ righe sono scritte le informazioni sulle pietre di ciascuna riga. Sulla $i+1$-esima riga ($1 \le i \le n$) è scritto $1$ intero $k_{i}$ ($0 \le k_{i} \le 10$) seguito da $2 \times k_{i}$ interi separati da spazi. Questi rappresentano le informazioni sulle pietre nella $i$-esima riga contando dalla riva di partenza.

$k_{i}$ rappresenta il numero di pietre presenti in quella riga e, per i successivi $2 \times k_{i}$ interi, il $2 \times j - 1$-esimo ($1 \le j \le k_{i}$) intero $x_{i,j}$ rappresenta il numero di colonna della $j$-esima pietra in quella riga, mentre il $2 \times j$-esimo intero $d_{i,j}$ rappresenta la scivolosità della $j$-esima pietra in quella riga. $x_{i,j}, d_{i,j}$ soddisfano rispettivamente $1 \le x_{i,j}, d_{i,j} \le 1000$.

Dei dati di test, il $20\%$ del punteggio soddisfa $n \le 6$, e un altro $20\%$ del punteggio soddisfa $m = 0$.

Dati di uscita

L'uscita consiste di $1$ sola riga contenente $1$ intero che rappresenta la somma minima del livello di pericolo dei salti per raggiungere la riva opposta.

Esempio

Nella Figura $4\text{-}2$, supponiamo che i numeri scritti sulle pietre rappresentino la scivolosità di ciascuna pietra. Attraversando le pietre nell'ordine indicato dalle frecce, i livelli di pericolo dei rispettivi salti sono, nell'ordine, $0$, $(2 + 2) \times 1 = 4$, $(2 + 1) \times 1 = 3$, $(1 + 4) \times 2 = 10$, $0$, e il totale è $17$. In questo caso, il totale del livello di pericolo dei salti è minimo.

Questo esempio corrisponde all'Esempio $1$.

Figura $4\text{-}2$: Esempio di percorso

Esempi di ingresso e uscita

L'ingresso e l'uscita corrispondenti all'esempio precedente sono mostrati nell'Esempio $1$.

Esempio di ingresso 1

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

Esempio di uscita 1

17

Esempio di ingresso 2

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

Esempio di uscita 2

40