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.