Domek z kart
Limit pamięci: 32 MB
Marcel dostał w tym roku na urodziny talię bardzo specyficznych kart.
Nie służą one do gry, lecz do budowania domków z kart.
Zaraz po rozpakowaniu prezentu niecierpliwy Marcel zbudował ogromną wieżę.
Zrobił to w następujący sposób: w pierwszej kolejności opierał karty parami o siebie,
następnie na powstałych szczytach stawiał kolejne karty, znów opierając
je parami o siebie, i tak dalej.
Okazało się, że na każdym piętrze, poza ostatnim, liczba szczytów była
parzysta, więc zawsze dało się poprawnie zbudować wyższe piętro.
Każda z kart w talii ma swoją wartość.
Teraz Marcel żałuje, że nie przemyślał lepiej swojej konstrukcji
i zużył zbyt dużo wartościowych kart. Znając wartość każdej karty,
chciałby zdjąć nie więcej niż kart z wieży tak, aby suma ich wartości
była jak największa. Oczywiście domek z kart nie może się przy tym zawalić!
Aby po wyjęciu kart domek nadal był stabilny, Marcel nie może nigdy
zdjąć pojedynczej karty, nie wyjmując zarazem jej pary (tzn. tej karty,
z którą nawzajem się podpierają).
Ponadto nigdy nie może zdjąć karty, nie zdjąwszy wcześniej wszystkich
kart, które są wyżej od niej i pośrednio lub bezpośrednio są o nią oparte.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby
całkowite i , , ,
oznaczające odpowiednio liczbę pięter karcianej wieży i maksymalną liczbę
kart, które Marcel może zdjąć.
Ponieważ karty można zdejmować tylko w parach, to będzie zawsze parzyste.
Kolejne wierszy wejścia zawiera opisy poszczególnych pięter wieży
od najwyższego do najniższego. W -szym wierszu znajduje się
liczb całkowitych , , ...,
(),
oznaczających wartości kart na -tym piętrze od góry, w
kolejności od lewej do prawej.
W testach wartych łącznie 50% punktów zachodzą dodatkowe ograniczenia:
, .
Wyjście
Twój program powinien wypisać na standardowe wyjście dokładnie jedną liczbę całkowitą
- maksymalną sumę wartości kart,
jaką Marcel może odzyskać, wyjmując maksymalnie kart z wieży, tak aby ta się nie zawaliła.
Przykład
Dla danych wejściowych:
3 6
1 -3
-10 1 2 1
1 1 3 2 -1 5 2 -3
poprawną odpowiedzią jest:
5
Karty, które Marcel powinien wyjąć z wieży, zostały zaznaczone na rysunku
liniami przerywanymi.
Mają one wartości: , , , , , , a więc suma ich wartości to .
Autor zadania: Michał Włodarczyk.