Énoncé du problème

Sur une certaine rivière, un jeu un peu dangereux consistant à sauter de pierre en pierre depuis une rive pour atteindre la rive opposée est très populaire.

Figure $4\text{-}1$ : Exemple de positions des pierres (Légendes japonaises sur la figure : 反対側の岸 = Rive opposée, 川 = Rivière, 始める岸 = Rive de départ, 列 = Colonne, 行 = Ligne)

Comme illustré sur la Figure $4\text{-}1$, on considère que les pierres se trouvent sur les cases d'une grille. Le nombre de lignes est $n$. Sur la Figure $4\text{-}1$, $n = 5$.

Dans ce jeu, en partant d'une rive, vous traversez jusqu'à la rive opposée en effectuant des sauts normaux ou au plus $m$ sauts sautant une ligne. Un saut normal consiste à sauter vers la rive ou l'une des pierres située $1$ ligne devant la ligne actuelle, et un saut sautant une ligne consiste à sauter vers la rive ou l'une des pierres située $2$ lignes devant la ligne actuelle. Ici, la ligne située $1$ ligne devant la rive de départ est la ligne $1$, celle située $2$ lignes devant est la ligne $2$, et la ligne située $2$ lignes devant la ligne $n-1$ ainsi que celle située $1$ ligne devant la ligne $n$ correspondent à la rive opposée.

Afin d'accomplir ce jeu de la manière la plus sûre possible, nous avons décidé de prendre en compte le niveau de danger d'un saut. Chaque pierre possède une glissance fixe. Lorsqu'on saute d'une pierre à une autre, qu'il s'agisse d'un saut normal ou d'un saut sautant une ligne, le niveau de danger du saut est défini par :

(glissance de la pierre actuelle $+$ glissance de la pierre d'arrivée) $\times$ (distance de déplacement horizontal)

Ici, la distance de déplacement horizontal est la différence entre les numéros de colonnes. De plus, le niveau de danger d'un saut d'une rive vers une pierre, ou d'une pierre vers une rive, est $0$.

Étant donnés $n, m$ ainsi que la position et la glissance de chaque pierre en entrée, écrivez un programme permettant de trouver la somme minimale possible des niveaux de danger des sauts pour atteindre la rive opposée. Pour les données d'entrée fournies, il est garanti qu'il est toujours possible d'atteindre la rive opposée, et qu'aucune case ne contient $2$ pierres ou plus.

Entrée

Sur la $1$-re ligne, $2$ entiers $n, m$ sont écrits, séparés par un espace. Ils représentent respectivement le nombre de lignes et le nombre autorisé de sauts sautant une ligne. $n, m$ vérifient respectivement $2 \le n \le 150$ et $0 \le m \le \frac{(n+1)}{2}$.

Sur les $n$ lignes suivantes, les informations sur les pierres de chaque ligne sont écrites. Sur la $i+1$-e ligne ($1 \le i \le n$), $1$ entier $k_{i}$ ($0 \le k_{i} \le 10$) suivi de $2 \times k_{i}$ entiers sont écrits, séparés par des espaces. Ils représentent les informations sur les pierres de la $i$-e ligne en comptant depuis la rive de départ.

$k_{i}$ représente le nombre de pierres présentes sur cette ligne, et parmi les $2 \times k_{i}$ entiers suivants, le $2 \times j - 1$-e ($1 \le j \le k_{i}$) entier $x_{i,j}$ représente le numéro de colonne de la $j$-e pierre de cette ligne, et le $2 \times j$-e entier $d_{i,j}$ représente la glissance de la $j$-e pierre de cette ligne. $x_{i,j}, d_{i,j}$ vérifient respectivement $1 \le x_{i,j}, d_{i,j} \le 1000$.

Parmi les données de test, $20\%$ des points vérifient $n \le 6$, et $20\%$ supplémentaires des points vérifient $m = 0$.

Sortie

La sortie consiste en $1$ ligne contenant $1$ entier représentant la somme minimale des niveaux de danger des sauts pour atteindre la rive opposée.

Exemple

Sur la Figure $4\text{-}2$, supposons que les nombres écrits sur les pierres représentent la glissance de chaque pierre. Lorsqu'on traverse les pierres dans l'ordre indiqué par les flèches, les niveaux de danger des sauts respectifs sont, dans l'ordre, $0$, $(2 + 2) \times 1 = 4$, $(2 + 1) \times 1 = 3$, $(1 + 4) \times 2 = 10$, $0$, et le total vaut $17$. Dans ce cas, la somme des niveaux de danger des sauts est minimale.

Cet exemple correspond à l'Exemple $1$.

Figure $4\text{-}2$ : Exemple de trajet

Exemples d'entrée et de sortie

L'entrée et la sortie correspondant à l'exemple ci-dessus sont présentées dans l'Exemple $1$.

Exemple d'entrée 1

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

Exemple de sortie 1

17

Exemple d'entrée 2

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

Exemple de sortie 2

40