Farmer Ron ב־Colorado בונה אתר סקי לפרות, אך התקציב מאפשר מעלית אחת. מסילה יחידה מחברת תמיכת בטון התחלתית לסופית דרך תמיכות ביניים, כל אחת בגובה0 מעל הקרקע. פלדה ישרה מחברת שכנות וחייבת להיות מעל הקרקע בכל נקודה.

FR חסכן ממזער תמיכות. מדד $N$ חלקות שוות $(2 \le N \le 5,000)$ עם גובה שלם $H$ $(0 \le H \le 1,000,000,000)$. בטיחות דורשת מרחק שכנים לכל היותר $K$ יחידות $(1 \le K \le N - 1)$. הפלדה קשיחה וישרה.

מצאו מינימום תמיכות: פלדה כולה מעל או משיקה לקרקע, מרחק שכנים אופקי לכל היותר $K$, תמיכות בחלקות הראשונה והאחרונה.

קלט

• שורה $1$: שני שלמים ברווח $N$, $K$.
• שורות $2..N+1$: שורה $i+1$ מכילה גובה שלם של חלקה $i$.

פלט

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

דוגמאות

קלט 1

13 4
0
1
0
2
4
6
8
6
8
8
9
11
12

פלט 1

5

הערה

5 תמיכות ב־1, 5, 7, 9, 13. הפלדה משיקה ב־4 מקומות:1–5, 5–7, 7–9, 12–13.

4 תמיכות ב־1, 5, 9, 13 מביאות פלדה מתחת לקרקע5–9. ב־1, 7, 13 היא מעל, אך7 ו־13 רחוקים אופקית יותר מ־4. אין פתרון עם פחות מ־5 ומרחקי שכנים עד4.

מקור הנוסח: https://github.com/ivankra/acm/blob/master/usaco/MAR06/prob/gold-en.htm

מחבר הבעיה: Adam Rosenfield, 2004