Alan's Candy Grams

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

AlanL received candy grams from his friend [REDACTED]! He has individual candies, which he organized in order to eat 1 for the next days such that each day has a specific associated candy. Each candy has a sweetness value of , and because [REDACTED] is sweet AlanL wishes to maximize the sweetness he eats over the days. However, if AlanL eats a 2 candies in a row with a sum greater than , he will spontaneously combust. Thus, sometimes AlanL must skip eating candies on certain days in order to live. Please help AlanL!

Input Specification

The first line will contain .

The next line will contain integers .

Output Specification

The maximum sweetness that AlanL can eat from the candies.

No further constraints.

Sample Input

5 5
5 1 2 3 4

Sample Output

6

Sample Explanation

Alan eats the second, third, and fourth candies.