Aufgabenstellung

An einem bestimmten Fluss ist ein etwas gefährliches Spiel beliebt, bei dem man von einem Ufer aus von Stein zu Stein springt, um das gegenüberliegende Ufer zu erreichen.

Abbildung $4\text{-}1$: Beispiel für Steinpositionen (Japanische Beschriftungen in der Abbildung: 反対側の岸 = Gegenüberliegendes Ufer, 川 = Fluss, 始める岸 = Startufer, 列 = Spalte, 行 = Zeile)

Wie in Abbildung $4\text{-}1$ dargestellt, betrachten wir nun die Steine als auf den Feldern eines Gitters liegend. Die Anzahl der Zeilen beträgt $n$. In Abbildung $4\text{-}1$ gilt $n = 5$.

Bei diesem Spiel startet man an einem Ufer und überquert den Fluss zum gegenüberliegenden Ufer, indem man normale Sprünge oder höchstens $m$ Sprünge, die eine Zeile überspringen, ausführt. Ein normaler Sprung ist ein Sprung ans Ufer oder auf einen der Steine in der Zeile, die $1$ Zeile vor der aktuellen Zeile liegt, und ein Sprung, der eine Zeile überspringt, ist ein Sprung ans Ufer oder auf einen der Steine in der Zeile, die $2$ Zeilen vor der aktuellen Zeile liegt. Hierbei ist die Zeile $1$ Zeile vor dem Startufer die Zeile $1$, die Zeile $2$ Zeilen davor ist die Zeile $2$, und sowohl die Zeile $2$ Zeilen vor der Zeile $n-1$ als auch die Zeile $1$ Zeile vor der Zeile $n$ sind das gegenüberliegende Ufer.

Um dieses Spiel so sicher wie möglich zu gestalten, haben wir beschlossen, den Gefahrengrad eines Sprungs zu betrachten. Jeder Stein hat eine feste Rutschigkeit. Wenn man von einem Stein auf einen anderen Stein springt – egal ob mit einem normalen Sprung oder einem Sprung, der eine Zeile überspringt –, ist der Gefahrengrad des Sprungs definiert als:

(Rutschigkeit des aktuellen Steins $+$ Rutschigkeit des Zielsteins) $\times$ (horizontale Bewegungsdistanz)

Hierbei ist die horizontale Bewegungsdistanz die Differenz zwischen den Spaltennummern. Außerdem beträgt der Gefahrengrad eines Sprungs vom Ufer auf einen Stein oder von einem Stein ans Ufer $0$.

Gegeben $n, m$ sowie die Position und Rutschigkeit jedes Steins als Eingabe, schreiben Sie ein Programm, das die minimal mögliche Gesamtsumme der Gefahrengrade der Sprünge beim Erreichen des gegenüberliegenden Ufers bestimmt. Für die gegebenen Eingabedaten ist garantiert, dass das gegenüberliegende Ufer immer erreicht werden kann und dass sich auf keinem Feld $2$ oder mehr Steine befinden.

Eingabe

In der $1$-ten Zeile stehen $2$ durch ein Leerzeichen getrennte ganze Zahlen $n, m$. Diese geben die Anzahl der Zeilen und die erlaubte Anzahl von Sprüngen an, die eine Zeile überspringen. $n, m$ erfüllen $2 \le n \le 150$ bzw. $0 \le m \le \frac{(n+1)}{2}$.

In den folgenden $n$ Zeilen stehen die Informationen über die Steine in jeder Zeile. In der $i+1$-ten Zeile ($1 \le i \le n$) steht $1$ ganze Zahl $k_{i}$ ($0 \le k_{i} \le 10$), gefolgt von $2 \times k_{i}$ durch Leerzeichen getrennten ganzen Zahlen. Diese geben die Informationen über die Steine in der $i$-ten Zeile, gezählt vom Startufer aus, an.

$k_{i}$ gibt die Anzahl der in dieser Zeile vorhandenen Steine an, und von den folgenden $2 \times k_{i}$ ganzen Zahlen gibt die $2 \times j - 1$-te ($1 \le j \le k_{i}$) ganze Zahl $x_{i,j}$ die Spaltennummer des $j$-ten Steins in dieser Zeile und die $2 \times j$-te ganze Zahl $d_{i,j}$ die Rutschigkeit des $j$-ten Steins in dieser Zeile an. $x_{i,j}, d_{i,j}$ erfüllen jeweils $1 \le x_{i,j}, d_{i,j} \le 1000$.

Von den Testdaten erfüllen $20\%$ der Punkte $n \le 6$ und weitere $20\%$ der Punkte erfüllen $m = 0$.

Ausgabe

Die Ausgabe besteht aus $1$ Zeile mit $1$ ganzen Zahl, welche die minimale Gesamtsumme der Gefahrengrade der Sprünge beim Erreichen des gegenüberliegenden Ufers angibt.

Beispiel

Nehmen wir an, dass in Abbildung $4\text{-}2$ die auf den Steinen geschriebenen Zahlen die Rutschigkeit des jeweiligen Steins angeben. Wenn man die Steine in der durch die Pfeile angegebenen Reihenfolge überquert, betragen die Gefahrengrade der jeweiligen Sprünge der Reihe nach $0$, $(2 + 2) \times 1 = 4$, $(2 + 1) \times 1 = 3$, $(1 + 4) \times 2 = 10$, $0$, und die Summe beträgt $17$. In diesem Fall ist die Gesamtsumme der Gefahrengrade der Sprünge minimal.

Dieses Beispiel entspricht Beispiel $1$.

Abbildung $4\text{-}2$: Beispiel einer Route

Beispieleingabe und -ausgabe

Die dem obigen Beispiel entsprechende Ein- und Ausgabe ist in Beispiel $1$ dargestellt.

Beispieleingabe 1

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

Beispielausgabe 1

17

Beispieleingabe 2

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

Beispielausgabe 2

40