- Time limit: 1.00 s
- Memory limit: 512 MB
Uolevi wants to form a secret society in Syrjälä. All of Syrjälä's inhabitants live along a very long road such that each house except the first and the last has two neighbors. Uolevi wants to recruit members to the secret society. For each house he knows that the resident of the house would add value to the society. In order to avoid awkward situations Uolevi doesn't want that any two members of the secret society are neighbors. Compute the maximum value of residents Uolevi can recruit.
Input
The first line of the input contains integer . The next line contains integers, .
Output
Output one integer, the maximum value for recruiting people to the secret society.
Constraints
Examples
Input:
6 5 2 6 3 3 7
Output:
18
Input:
4 2 10 7 1
Output:
11