โจทย์ปัญหา

ที่แม่น้ำแห่งหนึ่ง มีเกมที่ค่อนข้างอันตรายเล็กน้อยกำลังเป็นที่นิยม นั่นคือการกระโดดไปตามก้อนหินทีละก้อนจากฝั่งหนึ่งเพื่อไปยังฝั่งตรงข้าม

รูปที่ $4\text{-}1$: ตัวอย่างตำแหน่งของก้อนหิน (คำอธิบายภาษาญี่ปุ่นในรูป: 反対側の岸 = ฝั่งตรงข้าม, 川 = แม่น้ำ, 始める岸 = ฝั่งเริ่มต้น, 列 = คอลัมน์, 行 = แถว)

ทีนี้ ดังที่แสดงในรูปที่ $4\text{-}1$ เราจะพิจารณาว่าก้อนหินวางอยู่บนตารางสี่เหลี่ยม จำนวนแถวคือ $n$ ในรูปที่ $4\text{-}1$ ค่า $n = 5$

ในเกมนี้ เริ่มต้นจากฝั่งหนึ่ง คุณจะต้องข้ามไปยังฝั่งตรงข้ามโดยการกระโดดแบบปกติ หรือการกระโดดข้ามแถวไม่เกิน $m$ ครั้ง การกระโดดแบบปกติคือการกระโดดไปยังฝั่งหรือก้อนหินก้อนหนึ่งในแถวที่อยู่ถัดไปข้างหน้า $1$ แถวจากแถวปัจจุบัน และการกระโดดข้ามแถวคือการกระโดดไปยังฝั่งหรือก้อนหินก้อนหนึ่งในแถวที่อยู่ถัดไปข้างหน้า $2$ แถวจากแถวปัจจุบัน ในที่นี้ แถวที่อยู่ถัดไปข้างหน้า $1$ แถวจากฝั่งเริ่มต้นคือแถวที่ $1$ แถวที่อยู่ถัดไปข้างหน้า $2$ แถวคือแถวที่ $2$ และแถวที่อยู่ถัดไปข้างหน้า $2$ แถวจากแถวที่ $n-1$ รวมถึงแถวที่อยู่ถัดไปข้างหน้า $1$ แถวจากแถวที่ $n$ คือฝั่งตรงข้าม

เพื่อที่จะเล่นเกมนี้ให้สำเร็จอย่างปลอดภัยที่สุดเท่าที่จะทำได้ เราจึงตัดสินใจพิจารณาค่าความอันตรายของการกระโดด ก้อนหินแต่ละก้อนมีค่าความลื่นที่แน่นอน เมื่อกระโดดจากก้อนหินก้อนหนึ่งไปยังก้อนหินอีกก้อนหนึ่ง ไม่ว่าจะเป็นการกระโดดแบบปกติหรือการกระโดดข้ามแถว ค่าความอันตรายของการกระโดดจะถูกกำหนดดังนี้:

(ความลื่นของก้อนหินปัจจุบัน $+$ ความลื่นของก้อนหินปลายทาง) $\times$ (ระยะทางเคลื่อนที่ในแนวนอน)

โดยที่ระยะทางเคลื่อนที่ในแนวนอนคือผลต่างของหมายเลขคอลัมน์ นอกจากนี้ ค่าความอันตรายของการกระโดดจากฝั่งไปยังก้อนหิน หรือจากก้อนหินไปยังฝั่ง มีค่าเป็น $0$

เมื่อกำหนด $n, m$ และตำแหน่งกับความลื่นของก้อนหินแต่ละก้อนเป็นข้อมูลนำเข้า จงเขียนโปรแกรมเพื่อหาผลรวมค่าความอันตรายของการกระโดดที่น้อยที่สุดที่เป็นไปได้เมื่อไปถึงฝั่งตรงข้าม สำหรับข้อมูลนำเข้าที่กำหนดให้ รับประกันว่าจะสามารถไปถึงฝั่งตรงข้ามได้เสมอ และไม่มีช่องตารางใดที่มีก้อนหินตั้งแต่ $2$ ก้อนขึ้นไป

ข้อมูลนำเข้า

บรรทัดที่ $1$ มีจำนวนเต็ม $2$ จำนวนคือ $n, m$ คั่นด้วยช่องว่าง ซึ่งแทนจำนวนแถวและจำนวนครั้งที่อนุญาตให้กระโดดข้ามแถวตามลำดับ โดย $n, m$ สอดคล้องกับ $2 \le n \le 150$ และ $0 \le m \le \frac{(n+1)}{2}$ ตามลำดับ

ใน $n$ บรรทัดถัดไป เป็นข้อมูลของก้อนหินในแต่ละแถว ในบรรทัดที่ $i+1$ ($1 \le i \le n$) มีจำนวนเต็ม $1$ จำนวนคือ $k_{i}$ ($0 \le k_{i} \le 10$) ตามด้วยจำนวนเต็มอีก $2 \times k_{i}$ จำนวนคั่นด้วยช่องว่าง ซึ่งแทนข้อมูลของก้อนหินในแถวที่ $i$ นับจากฝั่งเริ่มต้น

$k_{i}$ แทนจำนวนก้อนหินที่มีอยู่ในแถวนั้น และสำหรับจำนวนเต็ม $2 \times k_{i}$ จำนวนที่ตามมา จำนวนเต็มตัวที่ $2 \times j - 1$ ($1 \le j \le k_{i}$) คือ $x_{i,j}$ แทนหมายเลขคอลัมน์ของก้อนหินก้อนที่ $j$ ในแถวนั้น และจำนวนเต็มตัวที่ $2 \times j$ คือ $d_{i,j}$ แทนความลื่นของก้อนหินก้อนที่ $j$ ในแถวนั้นตามลำดับ โดย $x_{i,j}, d_{i,j}$ สอดคล้องกับ $1 \le x_{i,j}, d_{i,j} \le 1000$ ตามลำดับ

ในข้อมูลที่ใช้ตรวจ คะแนนร้อยละ $20\%$ สอดคล้องกับ $n \le 6$ และคะแนนอีกร้อยละ $20\%$ สอดคล้องกับ $m = 0$

ข้อมูลส่งออก

ข้อมูลส่งออกประกอบด้วย $1$ บรรทัดที่มีจำนวนเต็ม $1$ จำนวน ซึ่งแทนผลรวมค่าความอันตรายของการกระโดดที่น้อยที่สุดเมื่อไปถึงฝั่งตรงข้าม

ตัวอย่าง

ในรูปที่ $4\text{-}2$ สมมติว่าตัวเลขที่เขียนอยู่บนก้อนหินแทนความลื่นของก้อนหินแต่ละก้อน เมื่อข้ามก้อนหินตามลำดับที่ลูกศรชี้ ค่าความอันตรายของการกระโดดแต่ละครั้งตามลำดับคือ $0$, $(2 + 2) \times 1 = 4$, $(2 + 1) \times 1 = 3$, $(1 + 4) \times 2 = 10$, $0$ และผลรวมคือ $17$ ในกรณีนี้ ผลรวมค่าความอันตรายของการกระโดดจะมีค่าน้อยที่สุด

ตัวอย่างนี้ตรงกับตัวอย่างที่ $1$

รูปที่ $4\text{-}2$: ตัวอย่างเส้นทาง

ตัวอย่างข้อมูลนำเข้าและส่งออก

ข้อมูลนำเข้าและส่งออกที่ตรงกับตัวอย่างข้างต้นแสดงอยู่ในตัวอย่างที่ $1$

ตัวอย่างข้อมูลนำเข้า 1

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

ตัวอย่างข้อมูลส่งออก 1

17

ตัวอย่างข้อมูลนำเข้า 2

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

ตัวอย่างข้อมูลส่งออก 2

40