You are walking along the street when a street vendor offers you a special deal. He has a row of ~N~ emeralds with different sizes. Each emerald has an integer weight between ~1~ and ~100~, inclusive, and the weights are clearly labelled for each emerald. However, the vendor tells you that you should not touch or buy the emeralds with odd-numbered weights as they have dangerous magical properties.
The vendor offers you to buy any number of consecutive emeralds from his row, as long as that selection of emeralds does not include any odd-weighted emeralds.
What is the largest total weight of emeralds you can buy with one purchase, following the rule above?
The input will consist of two lines. The first line contains ~N~, the number of emeralds in the vendor's row. The second line contains ~N~ space-separated integers between ~1~ and ~100~ inclusive, the weight of each emerald in the order that the vendor has them on display.
Please output one integer: the maximum possible sum of the weights of the emeralds that can be purchased as described above.
Constraints and Partial Marks
For ~5~ of the ~10~ available marks, ~1 \le N \le 3000~.
For the remaining ~5~ marks, ~1 \le N \le 10^5~.
13 2 3 4 4 5 6 1 2 2 2 1 8 2
Explanation of Sample Output
Buying the two rightmost emeralds, with sizes ~8~ and ~2~ (sum = ~10~), is the optimal purchase.
There are many suboptimal alternative purchases. These include:
- Buying the three consecutive emeralds with size ~2~ (sum = ~6~),
- Buying two of the three consecutive emeralds with size ~2~ (sum = ~4~),
- Buying the two consecutive emeralds with size ~4~ (sum = ~8~), or
- Buying a single emerald of size ~2~, ~4~, ~6~, or ~8~.