Treść zadania

Nad pewną rzeką popularna jest nieco niebezpieczna gra polegająca na przeskakiwaniu z kamienia na kamień z jednego brzegu, aby dotrzeć na przeciwległy brzeg.

Rysunek $4\text{-}1$: Przykład rozmieszczenia kamieni (Japońskie podpisy na rysunku: 反対側の岸 = Przeciwległy brzeg, 川 = Rzeka, 始める岸 = Brzeg startowy, 列 = Kolumna, 行 = Wiersz)

Teraz, jak pokazano na Rysunku $4\text{-}1$, przyjmujemy, że kamienie znajdują się na polach siatki. Liczba wierszy wynosi $n$. Na Rysunku $4\text{-}1$ mamy $n = 5$.

W tej grze, zaczynając z jednego brzegu, przeprawiasz się na przeciwległy brzeg, wykonując zwykłe skoki lub co najwyżej $m$ skoków z pominięciem jednego wiersza. Zwykły skok polega na przeskoczeniu na brzeg lub jeden z kamieni w wierszu położonym o $1$ wiersz dalej niż bieżący wiersz, natomiast skok z pominięciem jednego wiersza polega na przeskoczeniu na brzeg lub jeden z kamieni w wierszu położonym o $2$ wiersze dalej niż bieżący wiersz. Tutaj wierszem położonym o $1$ wiersz dalej niż brzeg startowy jest wiersz $1$, wierszem położonym o $2$ wiersze dalej jest wiersz $2$, natomiast wiersz położony o $2$ wiersze dalej niż wiersz $n-1$ oraz wiersz położony o $1$ wiersz dalej niż wiersz $n$ to przeciwległy brzeg.

Aby ukończyć tę grę możliwie najbezpieczniej, postanowiliśmy uwzględnić poziom niebezpieczeństwa skoku. Każdy kamień ma określoną śliskość. Podczas skoku z jednego kamienia na drugi – niezależnie od tego, czy jest to zwykły skok, czy skok z pominięciem jednego wiersza – poziom niebezpieczeństwa skoku definiuje się jako:

(śliskość bieżącego kamienia $+$ śliskość docelowego kamienia) $\times$ (odległość ruchu w poziomie)

Przy czym odległość ruchu w poziomie to różnica numerów kolumn. Ponadto poziom niebezpieczeństwa skoku z brzegu na kamień lub z kamienia na brzeg wynosi $0$.

Mając dane na wejściu liczby $n, m$ oraz pozycję i śliskość każdego kamienia, napisz program, który wyznaczy minimalną możliwą sumę poziomów niebezpieczeństwa skoków podczas docierania na przeciwległy brzeg. Dla podanych danych wejściowych gwarantowane jest, że zawsze można dotrzeć na przeciwległy brzeg oraz że na żadnym polu nie znajdują się $2$ lub więcej kamienie.

Wejście

W $1$-szym wierszu zapisane są $2$ liczby całkowite $n, m$ oddzielone spacją. Oznaczają one odpowiednio liczbę wierszy oraz dozwoloną liczbę skoków z pominięciem jednego wiersza. Liczby $n, m$ spełniają odpowiednio warunki $2 \le n \le 150$ oraz $0 \le m \le \frac{(n+1)}{2}$.

W kolejnych $n$ wierszach zapisane są informacje o kamieniach w poszczególnych wierszach. W $i+1$-szym wierszu ($1 \le i \le n$) zapisana jest $1$ liczba całkowita $k_{i}$ ($0 \le k_{i} \le 10$), po której następuje $2 \times k_{i}$ liczb całkowitych oddzielonych spacjami. Opisują one kamienie znajdujące się w $i$-tym wierszu, licząc od brzegu startowego.

$k_{i}$ oznacza liczbę kamieni znajdujących się w tym wierszu, a wśród kolejnych $2 \times k_{i}$ liczb całkowitych $2 \times j - 1$-sza ($1 \le j \le k_{i}$) liczba całkowita $x_{i,j}$ oznacza numer kolumny $j$-tego kamienia w tym wierszu, natomiast $2 \times j$-ta liczba całkowita $d_{i,j}$ oznacza śliskość $j$-tego kamienia w tym wierszu. Liczby $x_{i,j}, d_{i,j}$ spełniają odpowiednio warunek $1 \le x_{i,j}, d_{i,j} \le 1000$.

Spośród danych testowych $20\%$ punktów spełnia warunek $n \le 6$, a kolejne $20\%$ punktów spełnia warunek $m = 0$.

Wyjście

Wyjście składa się z $1$ wiersza zawierającego $1$ liczbę całkowitą oznaczającą minimalną sumę poziomów niebezpieczeństwa skoków podczas docierania na przeciwległy brzeg.

Przykład

Załóżmy, że na Rysunku $4\text{-}2$ liczby zapisane na kamieniach oznaczają śliskość poszczególnych kamieni. Podczas pokonywania kamieni w kolejności wskazanej strzałkami poziomy niebezpieczeństwa kolejnych skoków wynoszą odpowiednio $0$, $(2 + 2) \times 1 = 4$, $(2 + 1) \times 1 = 3$, $(1 + 4) \times 2 = 10$, $0$, a ich suma wynosi $17$. W tym przypadku suma poziomów niebezpieczeństwa skoków jest minimalna.

Ten przykład odpowiada Przykładowi $1$.

Rysunek $4\text{-}2$: Przykład trasy

Przykłady wejścia i wyjścia

Wejście i wyjście odpowiadające powyższemu przykładowi przedstawiono w Przykładzie $1$.

Przykładowe wejście 1

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

Przykładowe wyjście 1

17

Przykładowe wejście 2

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

Przykładowe wyjście 2

40