#H44. 【拓展题】打气球
【拓展题】打气球
Description
你最近对广场上摆摊打气球游戏非常感兴趣,于是准备大显身手。
你面前有一排气球,打中第 个气球的分数是 ,但摊主并不想让百发百中的你拿到所有分数,于是对气球做了一些手脚:当你射击第 个气球时,分数为 与 的所有气球也会被引爆,但只算第 个气球的分数,被引爆的气球无法射击。
你当然知道应该如何射击才能获得最大分数,但为了保证计算准确,让我们用程序进行计算。
Format
Input
第一行为一个整数 ,表示气球的数量
第二行为 个整数 ,为第 个气球的分数
Output
一个整数,表示可能获得的最大分数
Samples
2
1 2
2
3
1 2 3
4
9
1 2 1 3 2 2 2 2 3
10
3
1 3 5
9
Notes
注意数据范围