Đề bài

Ở một con sông nọ, có một trò chơi hơi nguy hiểm đang rất phổ biến: xuất phát từ một bờ sông, nhảy liên tiếp qua các hòn đá để sang bờ bên kia.

Hình $4\text{-}1$: Ví dụ về vị trí các hòn đá (Chú thích tiếng Nhật trong hình: 反対側の岸 = Bờ đối diện, 川 = Sông, 始める岸 = Bờ xuất phát, 列 = Cột, 行 = Hàng)

Bây giờ, như trong Hình $4\text{-}1$, ta coi các hòn đá nằm trên các ô của một lưới vuông. Số lượng hàng là $n$. Trong Hình $4\text{-}1$, $n = 5$.

Trong trò chơi này, bắt đầu từ một bờ sông, bạn sang bờ bên kia bằng cách thực hiện các cú nhảy thường hoặc tối đa $m$ cú nhảy cách dòng. Một cú nhảy thường là nhảy tới bờ hoặc một trong các hòn đá ở hàng phía trước hàng hiện tại $1$ hàng, còn cú nhảy cách dòng là nhảy tới bờ hoặc một trong các hòn đá ở hàng phía trước hàng hiện tại $2$ hàng. Ở đây, hàng phía trước bờ xuất phát $1$ hàng là hàng $1$, hàng phía trước $2$ hàng là hàng $2$, và hàng phía trước hàng $n-1$ đúng $2$ hàng cũng như hàng phía trước hàng $n$ đúng $1$ hàng chính là bờ đối diện.

Để thực hiện trò chơi này một cách an toàn nhất có thể, người ta quyết định xét mức độ nguy hiểm của mỗi cú nhảy. Mỗi hòn đá có một độ trơn cố định. Khi nhảy từ một hòn đá sang một hòn đá khác, dù là nhảy thường hay nhảy cách dòng, mức độ nguy hiểm của cú nhảy được định nghĩa là:

(độ trơn của hòn đá hiện tại $+$ độ trơn của hòn đá đích) $\times$ (khoảng cách di chuyển ngang)

Trong đó, khoảng cách di chuyển ngang là hiệu giữa hai chỉ số cột. Ngoài ra, mức độ nguy hiểm của cú nhảy từ bờ lên đá, hoặc từ đá lên bờ, là $0$.

Cho $n, m$ cùng vị trí và độ trơn của từng hòn đá làm đầu vào, hãy viết chương trình tìm giá trị nhỏ nhất của tổng mức độ nguy hiểm của các cú nhảy khi sang đến bờ đối diện. Dữ liệu đầu vào đảm bảo luôn có thể sang được bờ đối diện, và không có ô nào chứa từ $2$ hòn đá trở lên.

Dữ liệu vào

Dòng thứ $1$ ghi $2$ số nguyên $n, m$ cách nhau bởi dấu cách. Chúng biểu thị số hàng và số lần nhảy cách dòng tối đa được phép. $n, m$ lần lượt thỏa mãn $2 \le n \le 150$ và $0 \le m \le \frac{(n+1)}{2}$.

Trên $n$ dòng tiếp theo, mỗi dòng ghi thông tin về các hòn đá ở hàng tương ứng. Dòng thứ $i+1$ ($1 \le i \le n$) ghi $1$ số nguyên $k_{i}$ ($0 \le k_{i} \le 10$) và theo sau là $2 \times k_{i}$ số nguyên cách nhau bởi dấu cách. Chúng biểu thị thông tin về các hòn đá ở hàng thứ $i$ tính từ bờ xuất phát.

$k_{i}$ biểu thị số lượng hòn đá có ở hàng đó, và trong $2 \times k_{i}$ số nguyên tiếp theo, số nguyên thứ $2 \times j - 1$ ($1 \le j \le k_{i}$) là $x_{i,j}$ biểu thị chỉ số cột của hòn đá thứ $j$ trong hàng đó, còn số nguyên thứ $2 \times j$ là $d_{i,j}$ biểu thị độ trơn của hòn đá thứ $j$ trong hàng đó. $x_{i,j}, d_{i,j}$ lần lượt thỏa mãn $1 \le x_{i,j}, d_{i,j} \le 1000$.

Trong dữ liệu chấm, $20\%$ số điểm thỏa mãn $n \le 6$, và $20\%$ số điểm khác thỏa mãn $m = 0$.

Kết quả

In ra $1$ dòng chứa $1$ số nguyên biểu thị tổng mức độ nguy hiểm nhỏ nhất của các cú nhảy khi sang đến bờ đối diện.

Ví dụ

Trong Hình $4\text{-}2$, giả sử các số viết trên các hòn đá biểu thị độ trơn của mỗi hòn đá. Khi đi qua các hòn đá theo thứ tự mũi tên chỉ, mức độ nguy hiểm của từng cú nhảy lần lượt là $0$, $(2 + 2) \times 1 = 4$, $(2 + 1) \times 1 = 3$, $(1 + 4) \times 2 = 10$, $0$, và tổng cộng là $17$. Khi đó, tổng mức độ nguy hiểm của các cú nhảy là nhỏ nhất.

Ví dụ này tương ứng với Ví dụ mẫu $1$.

Hình $4\text{-}2$: Ví dụ về lộ trình

Ví dụ vào/ra

Dữ liệu vào và kết quả tương ứng với ví dụ trên được cho như ở Ví dụ mẫu $1$.

Dữ liệu vào mẫu 1

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

Kết quả mẫu 1

17

Dữ liệu vào mẫu 2

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

Kết quả mẫu 2

40