بيان المسألة

عند أحد الأنهار، تنتشر لعبة خطيرة قليلًا تتمثل في القفز من حجر إلى آخر انطلاقًا من إحدى الضفتين للوصول إلى الضفة المقابلة.

الشكل $4\text{-}1$: مثال على مواقع الأحجار (التسميات اليابانية في الشكل: 反対側の岸 = الضفة المقابلة، 川 = النهر، 始める岸 = ضفة البداية، 列 = عمود، 行 = صف)

الآن، كما هو موضح في الشكل $4\text{-}1$، نعتبر أن الأحجار موجودة على مربعات شبكة. عدد الصفوف هو $n$. في الشكل $4\text{-}1$، $n = 5$.

في هذه اللعبة، بدءًا من إحدى الضفتين، تعبر إلى الضفة المقابلة عن طريق القيام بقفزات عادية أو بما لا يزيد عن $m$ من القفزات التي تتخطى صفًا واحدًا. القفزة العادية هي القفز إلى الضفة أو إلى أحد الأحجار في الصف الذي يسبق الصف الحالي بصف $1$، والقفزة التي تتخطى صفًا واحدًا هي القفز إلى الضفة أو إلى أحد الأحجار في الصف الذي يسبق الصف الحالي بصفين $2$. هنا، الصف الذي يسبق ضفة البداية بصف $1$ هو الصف $1$، والصف الذي يسبقها بصفين $2$ هو الصف $2$، والصف الذي يسبق الصف $n-1$ بصفين $2$ وكذلك الصف الذي يسبق الصف $n$ بصف $1$ هما الضفة المقابلة.

الآن، من أجل إنجاز هذه اللعبة بأكبر قدر ممكن من الأمان، قررنا أخذ مستوى خطورة القفزة في الاعتبار. لكل حجر درجة انزلاق ثابتة. عند القفز من حجر إلى حجر آخر، سواء كانت قفزة عادية أو قفزة تتخطى صفًا واحدًا، يُعرَّف مستوى خطورة القفزة كما يلي:

(درجة انزلاق الحجر الحالي $+$ درجة انزلاق الحجر المقصود) $\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