#1216. [合肥市 2017] 体验积分值(point)

    ID: 1216 Type: Default 1000ms 256MiB Tried: 9 Accepted: 5 Difficulty: 9 Uploaded By: Tags>动态规划动态规划线性DP合肥市2017

[合肥市 2017] 体验积分值(point)

题目描述

卡卡西和小朋友们做完了烧脑的数字游戏,决定放松一下,他们来到了万达乐园,乐园中有很多的游玩项目,每玩一个项目就能获取一定的体验积分,不同的项目产生不同的体验积分,假设乐园所有的游乐项目正好排成一排,并且游客们不能游玩任意相邻的两个项目,那么卡卡西如何挑选游玩项目,使得这次万达行他能获得最多的体验积分值呢。

输入输出格式

输入

输入共两行,第一行是一个正整数 n,表示万达乐园的游乐项目数。第二行是 n 个用空格隔开的正整数,分别表示每个游乐项目的体验积分值。

输出

只有一个正整数,为最多的体验积分值。

输入输出样例

样例

输入1

5
3 10 8 20 21

输出1

32

输入2

5
3 17 8 20 21

输出2

38

数据范围/约定

1s, 256MB.

5≤n≤1000