Wyrównywanie terenu

Limit pamięci: 64 MB

Bajtazar postanowił wybudować dom. Jako lokalizację dla niego wybrał pewną bardzo wąską dolinę. Bajtazar musi najpierw wyrównać grunt pod budowę domu. Ma on do dyspozycji dwie koparki: pierwsza z nich może zwiększyć lub zmniejszyć poziom gruntu w dowolnym spójnym fragmencie doliny o dokładnie metrów; druga z nich może natomiast zwiększyć lub zmniejszyć poziom gruntu w dowolnym spójnym fragmencie doliny o dokładnie metrów. Zauważ, że zarówno przed wykonaniem każdej takiej operacji jak i po jej wykonaniu grunt w rozważanym kawałku doliny nie musi być równy.

Mając daną mapę terenu, wyznacz minimalną liczbę operacji, jakie trzeba wykonać, aby wyrównać teren w całej dolinie (tj. aby grunt w całej dolinie miał poziom równy 0). W trakcie wykonywania ciągu operacji poziom gruntu w każdym fragmencie doliny może być dowolnie duży lub dowolnie mały (w szczególności ujemny).

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite , , (, ), pooddzielane pojedynczymi odstępami. Liczba oznacza długość doliny, podaną w metrach. Drugi wiersz zawiera liczb całkowitych nieprzekraczających co do wartości bezwzględnej , pooddzielanych pojedynczymi odstępami. Liczby te reprezentują poziom gruntu (wyrażony w metrach) na kolejnych kawałkach ziemi długości jednego metra.

W testach wartych 30% punktów zachodzą dodatkowe warunki oraz .

W testach wartych 60% punktów zachodzą warunki oraz .

W testach wartych 90% punktów zachodzi warunek .

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę całkowitą - minimalną liczbę operacji potrzebnych do wyrównania gruntu lub liczbę , jeśli wyrównanie gruntu w dolinie za pomocą podanych koparek nie jest w ogóle możliwe.

Przykład

Dla danych wejściowych:

5 2 3
1 2 1 1 -1

poprawną odpowiedzią jest:

5

Wyjaśnienie do przykładu: Jedno z możliwych rozwiązań dla przykładowego wejścia to:

• zwiększ poziom gruntu na pierwszych dwóch metrach doliny o metry,
• zmniejsz poziom gruntu na pierwszych dwóch metrach doliny o metry,
• zwiększ poziom gruntu na czterech końcowych metrach doliny o metry,
• zwiększ poziom gruntu na ostatnim metrze doliny o metry,
• zmniejsz poziom gruntu na czterech końcowych metrach doliny o metry.

Autor zadania: Jakub Pachocki.