题目描述

设有 $N$ 个正整数（ $1 <= N <= 50$ ），其中每一个均是大于等于 1 、小于等于 300 的数。从这 $N$ 个数中任取出若干个数（不能取相邻的数），要求得到一种取法，使得到的和为最大。
例如：当 $N = 5$ 时，有 5 个数分别为：13，18，28，45，21
此时，有许多种取法， 如：

13，28，21 和为 62
13, 45 和为 58
18，45 和为 63
… … …

和为 63 应该是满足要求的一种取法。

输入格式

第一行是一个整数 $N$。

第二行有 $N$ 个符合条件的整数。

输出格式

一个整数，即最大和

样例

5
13 18 28 45 21

63

20
50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240

1500

10
1 2 3 4 5 6 7 8 9 10

30