Las vacas de Farmer John quieren saltar sobre la Luna como las de su canción infantil favorita. Por desgracia no pueden saltar.

El hechicero local preparó $P$ pociones ($1 \le P \le 150{,}000$) para ayudarlas. Deben tomarse estrictamente en orden de creación, aunque algunas pueden omitirse.

Cada poción tiene «fuerza» ($1 \le strength \le 500$) que mejora el salto. Tomarla en un paso impar aumenta el salto; en uno par lo disminuye. Antes de tomar pociones, la capacidad de salto es, por supuesto, 0.

Ninguna poción puede tomarse dos veces. Al empezar, hay que tomar una en cada paso desde el tiempo 1. Se pueden omitir una o más por turno.

Determina qué pociones tomar para el salto más alto.

Entrada

• Línea $1$: entero $P$.
• Líneas $2..P+1$: cada una contiene un entero, la fuerza de una poción. La línea 2 da la primera, la 3 la segunda, etc.

Salida

• Línea $1$: un entero, el máximo salto posible.

Ejemplos

Entrada 1

8
7
2
1
8
4
3
5
6

Salida 1

17