熙晨摘苹果

问题描述

果园里有 ( N ) 棵苹果树（( 1 \leq N \leq 50 )），每棵树上的苹果数大于等于1且小于等于10000。熙晨需要帮爷爷摘苹果，但不能摘取相邻的两棵树。求熙晨最多能摘到的苹果总数。

示例：
当 ( N = 5 ) 时，5棵树的苹果数为 13, 18, 28, 45, 21，部分摘法如下：

• 摘13、28、21，和为62
• 摘13、45，和为58
• 摘18、45，和为63（最优解）

输入格式

1. 第一行：整数 ( N )
2. 第二行：( N ) 个整数（用空格分隔），表示每棵树的苹果数

输出格式

一行整数，表示最多能摘到的苹果数

输入样例1

5
13 18 28 45 21

输出样例1

63