Farmer Ron in Colorado baut einen Skikurort für Kühe, das Budget erlaubt nur einen Lift. Eine Einschienenbahn verbindet den Betonstartträger mit dem Endträger über Zwischenstützen, jede0 hoch über ihrem Boden. Gerade Stahlabschnitte verbinden Nachbarn und müssen überall über dem Boden liegen.

Sparsam will FR Stützen minimieren. Er vermisst $N$ gleich große Grundstücke $(2 \le N \le 5,000)$ mit ganzzahliger Höhe $H$ $(0 \le H \le 1,000,000,000)$. Sicherheitsregeln erlauben Nachbarabstand höchstens $K$ Einheiten $(1 \le K \le N - 1)$. Stahl ist starr und gerade.

Finde minimale Stützen: Stahl ganz über oder tangential zum Boden, horizontaler Nachbarabstand höchstens $K$, Stützen auf erstem und letztem Grundstück.

Eingabe

• Zeile $1$: zwei ganze Zahlen mit Leerzeichen $N$, $K$.
• Zeilen $2..N+1$: Zeile $i+1$ enthält die ganzzahlige Höhe von Grundstück $i$.

Ausgabe

• Zeile $1$: eine ganze Zahl, die minimale Turmanzahl unter diesen Bedingungen.

Beispiele

Eingabe 1

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

Ausgabe 1

5

Hinweis

5 Stützen in1, 5, 7, 9, 13. Stahl berührt den Boden an4 Stellen:1–5, 5–7, 7–9, 12–13.

4 Stützen in1, 5, 9, 13 bringen Stahl unter Boden5–9. Bei1, 7, 13 liegt er darüber, aber7 und13 sind horizontal über4 auseinander. Weniger als5 Stützen mit Nachbarabstand höchstens4 ist unmöglich.

Originalquelle: https://github.com/ivankra/acm/blob/master/usaco/MAR06/prob/gold-en.htm

Aufgabenautor: Adam Rosenfield, 2004