Na ulici sa nachádza $n$ domov usporiadaných v jednom rade. Mokrí banditi[^1] sa rozhodli túto ulicu navštíviť s cieľom ukradnúť čo najviac peňazí. O každom dome je známe, koľko peňazí sa v ňom nachádza.
Aby však nepritiahli pozornosť, nesmú vykradnúť dva susedné domy.
Akú maximálnu sumu peňazí si môžu z tejto ulice odniesť?
Na prvom riadku vstupu dostanete číslo $n$. Na druhom riadku vstupu dostanete $n$ medzerou oddelených nezáporných čísiel $h_i$ -- hodnoty jednotlivých domov.
Na výstup vypíšte jedno číslo -- maximálna hodnota, ktorú môžu banditi získať.
5
3 2 8 1 4
15