תיאור הבעיה

בנהר מסוים נפוץ משחק מעט מסוכן שבו קופצים מאבן לאבן מגדה אחת כדי להגיע אל הגדה הנגדית.

איור $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