Given an array of (positive) integers, find a subset with the maximal sum.
However, there is the additional restriction that no two numbers in the subset may be adjacent.

For example, for the array ~4, 5, 6, 9, 10~:
~4, 6, 10~ is valid, while ~5, 9, 10~ is invalid since ~9~ and ~10~ are next to each other.
~4, 6, 10~ happens to be the optimal sum in this case, so ~20~ is the answer.

Input Specification

An integer ~1 < N \le 100\,000~.
~N~ lines, each with one positive integer in the sequence ~\le 1\,000~.

Output Specification

The maximum sum possible.