Farmer Ron w Colorado buduje ośrodek narciarski dla krów, budżet pozwala tylko na jeden wyciąg. Jednoszynowy łączy betonową podporę początkową z końcową przez pośrednie, każda wysokości0 nad ziemią. Prosta stal łączy sąsiadów i musi wszędzie być ponad ziemią.

Oszczędny FR minimalizuje podpory. Zmierzył $N$ równych działek $(2 \le N \le 5,000)$ z całkowitą wysokością $H$ $(0 \le H \le 1,000,000,000)$. Bezpieczeństwo wymaga odstępu sąsiadów najwyżej $K$ jednostek $(1 \le K \le N - 1)$. Stal sztywna jest prosta.

Znajdź minimum podpór: stal cała nad ziemią lub styczna, poziome odstępy sąsiadów najwyżej $K$, podpory na pierwszej i ostatniej działce.

Wejście

• Wiersz $1$: dwie całkowite ze spacją $N$, $K$.
• Wiersze $2..N+1$: wiersz $i+1$ ma całkowitą wysokość działki $i$.

Wyjście

• Wiersz $1$: całkowita, minimum wież spełniających warunki.

Przykład

Wejście 1

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

Wyjście 1

5

Uwagi

5 podpór w1, 5, 7, 9, 13. Stal styczna w4 miejscach:1–5, 5–7, 7–9, 12–13.

4 podpory w1, 5, 9, 13 dają stal pod ziemią5–9. Przy1, 7, 13 jest nad ziemią, ale7 i13 mają odstęp poziomy ponad4. Mniej niż5 podpór z sąsiednimi odstępami najwyżej4 jest niemożliwe.

Źródło oryginału: https://github.com/ivankra/acm/blob/master/usaco/MAR06/prob/gold-en.htm

Autor zadania: Adam Rosenfield, 2004