Deskripsi Masalah

Di suatu sungai, sebuah permainan yang agak berbahaya yaitu melompat dari batu ke batu dari satu tepi sungai untuk mencapai tepi seberang sedang populer.

Gambar $4\text{-}1$: Contoh posisi batu (Label bahasa Jepang pada gambar: 反対側の岸 = Tepi seberang, 川 = Sungai, 始める岸 = Tepi awal, 列 = Kolom, 行 = Baris)

Sekarang, seperti yang ditunjukkan pada Gambar $4\text{-}1$, kita menganggap batu-batu tersebut berada pada petak-petak kisi. Jumlah baris adalah $n$. Pada Gambar $4\text{-}1$, $n = 5$.

Dalam permainan ini, dimulai dari satu tepi sungai, Anda menyeberang ke tepi seberang dengan melakukan lompatan biasa atau paling banyak $m$ lompatan melewati satu baris. Lompatan biasa adalah melompat ke tepi sungai atau salah satu batu pada baris yang berada $1$ baris di depan baris saat ini, sedangkan lompatan melewati satu baris adalah melompat ke tepi sungai atau salah satu batu pada baris yang berada $2$ baris di depan baris saat ini. Di sini, baris yang berada $1$ baris di depan tepi awal adalah baris $1$, baris yang berada $2$ baris di depan adalah baris $2$, serta baris yang berada $2$ baris di depan baris $n-1$ dan baris yang berada $1$ baris di depan baris $n$ adalah tepi seberang.

Sekarang, untuk menyelesaikan permainan ini dengan seaman mungkin, kita memutuskan untuk mempertimbangkan tingkat bahaya dari suatu lompatan. Setiap batu memiliki tingkat kelicinan yang tetap. Saat melompat dari satu batu ke batu lainnya, baik itu lompatan biasa maupun lompatan melewati satu baris, tingkat bahaya lompatan didefinisikan sebagai:

(kelicinan batu saat ini $+$ kelicinan batu tujuan) $\times$ (jarak perpindahan horizontal)

Di sini, jarak perpindahan horizontal adalah selisih antara nomor kolom. Selain itu, tingkat bahaya lompatan dari tepi sungai ke batu, atau dari batu ke tepi sungai, adalah $0$.

Diberikan $n, m$ serta posisi dan kelicinan setiap batu sebagai masukan, buatlah program untuk mencari nilai minimum dari total tingkat bahaya lompatan saat mencapai tepi seberang. Untuk data masukan yang diberikan, dijamin selalu mungkin untuk mencapai tepi seberang, dan tidak ada petak yang berisi $2$ batu atau lebih.

Format Masukan

Pada baris ke-$1$, tertulis $2$ bilangan bulat $n, m$ yang dipisahkan oleh spasi. Bilangan-bilangan ini menyatakan jumlah baris dan jumlah lompatan melewati satu baris yang diizinkan. $n, m$ masing-masing memenuhi $2 \le n \le 150$ dan $0 \le m \le \frac{(n+1)}{2}$.

Pada $n$ baris berikutnya, tertulis informasi mengenai batu-batu pada setiap baris. Pada baris ke-$i+1$ ($1 \le i \le n$), tertulis $1$ bilangan bulat $k_{i}$ ($0 \le k_{i} \le 10$) diikuti oleh $2 \times k_{i}$ bilangan bulat yang dipisahkan oleh spasi. Bilangan-bilangan ini menyatakan informasi mengenai batu-batu pada baris ke-$i$ dihitung dari tepi awal.

$k_{i}$ menyatakan jumlah batu yang ada pada baris tersebut, dan untuk $2 \times k_{i}$ bilangan bulat berikutnya, bilangan bulat ke-$2 \times j - 1$ ($1 \le j \le k_{i}$) yaitu $x_{i,j}$ menyatakan nomor kolom dari batu ke-$j$ pada baris tersebut, dan bilangan bulat ke-$2 \times j$ yaitu $d_{i,j}$ menyatakan kelicinan dari batu ke-$j$ pada baris tersebut. $x_{i,j}, d_{i,j}$ masing-masing memenuhi $1 \le x_{i,j}, d_{i,j} \le 1000$.

Dari data uji, $20\%$ dari skor memenuhi $n \le 6$, dan $20\%$ lainnya dari skor memenuhi $m = 0$.

Format Keluaran

Keluaran terdiri dari $1$ baris yang berisi $1$ bilangan bulat yang menyatakan total tingkat bahaya lompatan minimum saat mencapai tepi seberang.

Contoh

Pada Gambar $4\text{-}2$, misalkan angka-angka yang tertulis pada batu menyatakan kelicinan masing-masing batu. Saat menyeberangi batu-batu sesuai urutan yang ditunjukkan oleh panah, tingkat bahaya dari masing-masing lompatan secara berurutan adalah $0$, $(2 + 2) \times 1 = 4$, $(2 + 1) \times 1 = 3$, $(1 + 4) \times 2 = 10$, $0$, dan totalnya adalah $17$. Dalam kasus ini, total tingkat bahaya lompatan menjadi minimum.

Contoh ini bersesuaian dengan Contoh $1$.

Gambar $4\text{-}2$: Contoh rute

Contoh Masukan dan Keluaran

Masukan dan keluaran yang bersesuaian dengan contoh di atas ditunjukkan pada Contoh $1$.

Contoh Masukan 1

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

Contoh Keluaran 1

17

Contoh Masukan 2

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

Contoh Keluaran 2

40