Farmer John הוא אשף חשבונאות מדהים והבין שעלול להיגמר לו הכסף להפעלת החווה. הוא חישב ורשם בדיוק את ההוצאה ($1 \le money_{i} \le 10,000$) בכל אחד מ־$N$ הימים הבאים ($1 \le N \le 100,000$).

FJ רוצה תקציב לרצף של בדיוק $M$ תקופות כספיות ($1 \le M \le N$), בשם ״fajomonths״. כל תקופה כוללת יום אחד או יותר רצופים, וכל יום שייך בדיוק לתקופה אחת.

הוא רוצה לסדר את התקופות כדי למזער את הוצאת התקופה היקרה ביותר וכך לקבוע מגבלה חודשית.

קלט

שורה 1: שני שלמים מופרדים ברווח, $N$ ו־$M$. שורות $2\ldots N+1$: שורה $i+1$ מכילה את מספר הדולרים ש־Farmer John מוציא ביום ה־$i$.

פלט

שורה 1: המגבלה החודשית הקטנה ביותר ש־Farmer John יכול להסתדר איתה.

דוגמאות

קלט 1

7 5
100
400
300
100
500
101
400

פלט 1

500

הערה

אם היומיים הראשונים חודש, השלישי והרביעי חודש, וכל אחד משלושת האחרונים חודש נפרד, הוא מוציא לכל היותר 500 דולר בחודש. כל חלוקה אחרת נותנת מגבלה חודשית מזערית גדולה יותר.

מקור הבעיה: USACO, מרץ 2007.