Les vaches de Farmer John veulent sauter par-dessus la Lune comme dans leur comptine préférée. Malheureusement, elles ne peuvent pas sauter.

Le sorcier local a préparé $P$ potions ($1 \le P \le 150{,}000$) pour les aider. Il faut les prendre strictement dans leur ordre de création, mais certaines peuvent être ignorées.

Chaque potion a une «force» ($1 \le strength \le 500$) améliorant le saut. La prendre à un instant impair augmente le saut ; à un instant pair, elle le diminue. Avant toute potion, la capacité de saut est bien sûr 0.

Aucune potion ne peut être prise deux fois. Dès le début, il faut en prendre une à chaque instant à partir de 1. À chaque tour, une ou plusieurs potions peuvent être ignorées.

Déterminez quelles potions prendre pour le saut le plus haut.

Entrée

• Ligne $1$ : entier $P$.
• Lignes $2..P+1$ : chacune contient un entier, la force d’une potion. La ligne 2 donne la première, la ligne 3 la deuxième, et ainsi de suite.

Sortie

• Ligne $1$ : un entier, le saut maximal possible.

Exemples

Entrée 1

8
7
2
1
8
4
3
5
6

Sortie 1

17