Problem description

Back
Show PDF
Maratończyk
(E)
Limit pamięci: 256 MB
Limit czasu: 1.00 s

Pewien biegacz postanowił wziąć udział w morderczym ultramaratonie składającym się z N kolejnych odcinków trasy. Pokonanie i-tego odcinka o własnych siłach wymaga zużycia dokładnie Ai jednostek energii.

Przed startem maratończyk ma w pełni naładowany zapas energii równy X. W trakcie zawodów może co najwyżej K razy skorzystać ze specjalnej taksówki dla biegaczy.

Skorzystanie z taksówki na danym odcinku niesie ze sobą dwie korzyści: 1. Biegacz nie zużywa na nim ani jednej jednostki energii. 2. Podczas jazdy odpoczywa, dzięki czemu po opuszczeniu pojazdu poziom jego energii wynosi ponownie dokładnie X (niezależnie od tego, ile energii zostało mu przed wejściem).

Pomóż biegaczowi obliczyć minimalną początkową pojemność energii X, która pozwoli mu ukończyć całą trasę tak, aby w żadnym momencie poziom energii nie spadł poniżej zera.

Wejście

W Pierwszy wierszu wejścia znajdują się dwie liczby całkowite N oraz K oznaczające odpowiednio liczbę odcinków maratonu oraz maksymalną liczbę dozwolonych przejazdów taksówką.

Drugi wiersz wejścia zawiera N liczb całkowitych A1, A2, …, AN (1 ≤ Ai ≤ 109) pooddzielanych pojedynczymi odstępami, określających koszt energetyczny pokonania kolejnych odcinków.

Wyjście

Twój program powinien wypisać jedną liczbę całkowitą — minimalny początkowy poziom energii X, z którym maratończyk może ukończyć bieg.

Ograniczenia

1 ≤ N ≤ 105, 0 ≤ K ≤ N, 1 ≤ Ai ≤ 109

Przykład

Wejście Wyjście Wyjaśnienie 
5 2
5 8 3 7 4

5
  1. Startuje z energią 5. Po przebiegnięciu zostaje mu 5 − 5 = 0.
  2. Bierze taksówkę (1. użycie). Wysiada z pełną energią 5.
  3. Biegnie o własnych siłach; zostaje mu 5 − 3 = 2.
  4. Bierze taksówkę (2. użycie). Wysiada z energią 5.
  5. Biegnie o własnych siłach; zostaje mu 5 − 4 = 1 ≥ 0.
Wejście Wyjście 
4 0
4 2 3 5

14

Ocenianie

Podzadanie Warunki Punkty
1 K = 1 15
2 N ≤ 20 15
3 N ≤ 1000 30
4 Brak dodatkowych ograniczeń 40