Коровы Farmer John хотят перепрыгнуть Луну, как в любимой детской песенке. К сожалению, коровы не умеют прыгать.

Местный знахарь приготовил $P$ зелий ($1 \le P \le 150{,}000$), помогающих прыгать. Принимать их нужно строго в порядке приготовления, хотя некоторые можно пропускать.

У каждого зелья есть «сила» ($1 \le strength \le 500$), усиливающая прыжки. В нечётный момент приём увеличивает прыжок, в чётный — уменьшает. До приёма зелий способность к прыжкам, конечно, равна 0.

Нельзя принимать зелье дважды. После начала приёма нужно принимать по одному в каждый момент начиная с 1. За ход можно пропустить одно или несколько зелий.

Определите, какие зелья принять для максимального прыжка.

Входные данные

• Строка $1$: целое $P$.
• Строки $2..P+1$: каждая содержит целое — силу зелья. Строка 2 задаёт первое, строка 3 — второе, и так далее.

Выходные данные

• Строка $1$: одно целое — максимально возможный прыжок.

Примеры

Входные данные 1

8
7
2
1
8
4
3
5
6

Выходные данные 1

17