Paul הוא בעל חברת קייטרינג, והעסקים פורחים. לחברה יש $k$ צוותי קייטרינג, שכל אחד מהם אחראי למערכת ציוד אחת. מדי שבוע החברה מקבלת $n$ בקשות לקייטרינג לאירועים שונים. לכל בקשה היא שולחת צוות עם הציוד שלו למקום האירוע. הצוות מביא את האוכל, מתקין את הציוד ומדריך את המארח כיצד להשתמש בציוד ולהגיש את האוכל. אחרי האירוע, המארח אחראי להחזיר את הציוד לחברה של Paul.

תמונה מתוך Wikimedia Commons

למרבה הצער, בחלק מהשבועות מספר הצוותים קטן ממספר הבקשות, ולכן ייתכן שצוותים מסוימים יצטרכו לטפל ביותר מאירוע אחד. במקרים כאלה החברה אינה יכולה לחכות שהמארח יחזיר את הציוד, ועליה להשאיר את הצוות במקום כדי להעביר את הציוד למקום אחר. לחברה יש הערכה מדויקת של עלות העברת מערכת ציוד מכל מקום לכל מקום אחר. בהינתן העלויות האלה, Paul רוצה להכין Advance Catering Map כדי לטפל בבקשות תוך מזעור העלות הכוללת של העברת הציוד (כולל ההעברה הראשונה), גם אם הדבר מחייב שלא להשתמש בכל הצוותים הזמינים. Paul זקוק לעזרתכם בכתיבת תוכנית לביצוע המשימה. הבקשות ממוינות בסדר עולה של זמני האירועים ונבחרות כך שלכל $i<j$ יש די זמן להעביר את הציוד ששימש בבקשה ה-$i$ אל מקום הבקשה ה-$j$.

קלט

השורה הראשונה בקלט מכילה שני מספרים שלמים $n$ ($1 \le n \le 100$) ו-$k$ ($1 \le k \le 100$), שהם מספר הבקשות ומספר צוותי הקייטרינג, בהתאמה. לאחר מכן מופיעות $n$ שורות, כאשר השורה ה-$i$ מכילה $n-i+1$ מספרים שלמים בין $0$ ל-$1\,000\,000$, כולל הקצוות. המספר ה-$j$ בשורה ה-$i$ הוא עלות העברת מערכת ציוד ממקום $i$ למקום $i+j$. החברה נמצאת במקום $1$, ו-$n$ הבקשות נמצאות במקומות $2$ עד $n+1$.

פלט

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

דוגמאות

קלט 1

3 2
40 30 40
50 10
50

פלט 1

80

קלט 2

3 2
10 10 10
20 21
21

פלט 2

40