Enunciado del problema
En cierto río, está de moda un juego algo peligroso que consiste en saltar de piedra en piedra desde una orilla hasta llegar a la orilla opuesta.
Figura $4\text{-}1$: Ejemplo de posiciones de las piedras (Etiquetas en japonés en la figura: 反対側の岸 = Orilla opuesta, 川 = Río, 始める岸 = Orilla inicial, 列 = Columna, 行 = Fila)
Ahora, como se muestra en la Figura $4\text{-}1$, consideramos que las piedras existen sobre las casillas de una cuadrícula. El número de filas es $n$. En la Figura $4\text{-}1$, $n = 5$.
En este juego, comenzando desde una orilla, cruzas hasta la orilla opuesta realizando saltos normales o a lo sumo $m$ saltos que omiten una fila. Un salto normal consiste en saltar a la orilla o a una de las piedras en la fila que está $1$ fila por delante de la fila actual, y un salto que omite una fila consiste en saltar a la orilla o a una de las piedras en la fila que está $2$ filas por delante de la fila actual. Aquí, la fila que está $1$ fila por delante de la orilla inicial es la fila $1$, la fila que está $2$ filas por delante es la fila $2$, y tanto la fila que está $2$ filas por delante de la fila $n-1$ como la fila que está $1$ fila por delante de la fila $n$ son la orilla opuesta.
Ahora bien, para completar este juego de la manera más segura posible, decidimos considerar el nivel de peligro de un salto. Cada piedra tiene una resbaladicidad fija. Al saltar de una piedra a otra, ya sea mediante un salto normal o un salto que omite una fila, el nivel de peligro del salto se define como:
(resbaladicidad de la piedra actual $+$ resbaladicidad de la piedra de destino) $\times$ (distancia de desplazamiento horizontal)
Aquí, la distancia de desplazamiento horizontal es la diferencia entre los números de columna. Además, el nivel de peligro de un salto desde una orilla a una piedra, o desde una piedra a una orilla, es $0$.
Dados $n, m$ y la posición y resbaladicidad de cada piedra como entrada, escribe un programa para encontrar el mínimo total posible del nivel de peligro de los saltos al llegar a la orilla opuesta. Para los datos de entrada proporcionados, se garantiza que siempre es posible llegar a la orilla opuesta y que ninguna casilla contiene $2$ o más piedras.
Entrada
En la $1$-a línea se escriben $2$ enteros $n, m$ separados por un espacio. Estos representan el número de filas y el número permitido de saltos que omiten una fila. $n, m$ satisfacen $2 \le n \le 150$ y $0 \le m \le \frac{(n+1)}{2}$, respectivamente.
En las siguientes $n$ líneas se escribe la información sobre las piedras de cada fila. En la línea $i+1$ ($1 \le i \le n$), se escribe $1$ entero $k_{i}$ ($0 \le k_{i} \le 10$) seguido de $2 \times k_{i}$ enteros separados por espacios. Estos representan la información sobre las piedras en la $i$-ésima fila contando desde la orilla inicial.
$k_{i}$ representa el número de piedras que existen en esa fila, y para los siguientes $2 \times k_{i}$ enteros, el entero $2 \times j - 1$-ésimo ($1 \le j \le k_{i}$), $x_{i,j}$, representa el número de columna de la $j$-ésima piedra en esa fila, y el entero $2 \times j$-ésimo, $d_{i,j}$, representa la resbaladicidad de la $j$-ésima piedra en esa fila, respectivamente. $x_{i,j}, d_{i,j}$ satisfacen $1 \le x_{i,j}, d_{i,j} \le 1000$, respectivamente.
De los datos de prueba, el $20\%$ de la puntuación satisface $n \le 6$, y otro $20\%$ de la puntuación satisface $m = 0$.
Salida
La salida consta de $1$ línea que contiene $1$ entero que representa la suma mínima del nivel de peligro de los saltos al llegar a la orilla opuesta.
Ejemplo
En la Figura $4\text{-}2$, supongamos que los números escritos en las piedras representan la resbaladicidad de cada piedra. Al cruzar las piedras en el orden indicado por las flechas, los niveles de peligro de los saltos respectivos son, en orden, $0$, $(2 + 2) \times 1 = 4$, $(2 + 1) \times 1 = 3$, $(1 + 4) \times 2 = 10$, $0$, y el total es $17$. En este caso, el total del nivel de peligro de los saltos es mínimo.
Este ejemplo corresponde al Ejemplo $1$.
Figura $4\text{-}2$: Ejemplo de una ruta
Ejemplo de entrada y salida
La entrada y la salida correspondientes al ejemplo anterior son las que se muestran en el Ejemplo $1$.
Entrada de ejemplo 1
5 1 2 1 3 2 2 1 3 2 1 1 7 1 2 1 1 4 4
Salida de ejemplo 1
17
Entrada de ejemplo 2
5 0 2 1 3 2 2 1 3 2 1 1 7 1 2 1 1 4 4
Salida de ejemplo 2
40