Krowy Farmer John chcą przeskoczyć Księżyc jak w ulubionej rymowance. Niestety nie potrafią skakać.

Miejscowy szaman przygotował $P$ mikstur ($1 \le P \le 150{,}000$), by pomóc. Trzeba je przyjmować dokładnie w kolejności powstania, choć niektóre można pominąć.

Każda ma „siłę” ($1 \le strength \le 500$) wzmacniającą skok. Przyjęcie w nieparzystym kroku zwiększa skok, w parzystym zmniejsza. Przed miksturami zdolność skoku wynosi oczywiście 0.

Nie wolno brać mikstury dwa razy. Po rozpoczęciu należy brać jedną na krok, począwszy od czasu 1. W turze można pominąć jedną lub więcej.

Wybierz mikstury dla najwyższego skoku.

Wejście

• Wiersz $1$: całkowite $P$.
• Wiersze $2..P+1$: każdy zawiera całkowitą siłę mikstury. Wiersz 2 daje pierwszą, 3 drugą, i tak dalej.

Wyjście

• Wiersz $1$: jedna liczba całkowita, maksymalny możliwy skok.

Przykład

Wejście 1

8
7
2
1
8
4
3
5
6

Wyjście 1

17