הפרות רוצות להיות ספורטאיות טובות יותר, ולכן Bessie מתאמנת במסלול בדיוק $N$ $(1 \le N \le 10,000)$ דקות. בכל דקה היא בוחרת לרוץ או לנוח במשך כל הדקה.

המרחק הסופי תלוי ב״מקדם העייפות״, שמתחיל ב-0. ריצה בדקה $i$ עוברת בדיוק מרחק $D_i$ $(1 \le D_i \le 1,000)$ ומעלה את המקדם ב-1, אך אסור שיעבור אי פעם את $M$ $(1 \le M \le 500)$. מנוחה מורידה 1 בכל דקה. היא לא יכולה להתחיל לרוץ שוב עד שיגיע ל-0; אז אפשר לרוץ או לנוח.

בסוף $N$ הדקות המקדם של Bessie חייב להיות בדיוק 0, אחרת לא תישאר אנרגיה לשאר היום.

מצאו את מרחק הריצה המרבי.

קלט

קראו מהקלט התקני.

• שורה 1: שלמים $N$ ו-$M$ מופרדים ברווח.
• שורות $2..N+1$: שורה $i+1$ מכילה שלם יחיד $D_i$.

פלט

כתבו לפלט התקני.

• שורה 1: שלם יחיד, המרחק המרבי המקיים את התנאים.

דוגמאות

קלט 1

5 2
5
3
4
2
10

פלט 1

9

הערה

Bessie רצה בדקה הראשונה ($distance=5$), נחה בשנייה, רצה בשלישית ($distance=4$), נחה ברביעית ובחמישית. בחמישית אי אפשר לרוץ כי העייפות הסופית לא תהיה 0.

מחבר: Neal Wu, 2007