#2012. 小学生的复仇

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 192023211995

题目描述

小学生取舍非常想玩王者荣耀,但是他的妈妈告诉他,他需要在小猿口算上进行pk,赢一次就能够玩一个小时的王者荣耀,但是最近大学生不讲武德,天天在pk里炸鱼,导致他一把也没有赢,因此一把王者也没有玩到,他非常愤怒。

为了报复大学生,他请自己的研究生哥哥ikun出了一道题并放入小猿口算的题库中,为了保证取舍能够稳赢大学生,ikun结合了小学生最喜欢的跳格子。

给你一个长度为 的正整数数组

你的目标是从 出发,到达 处。若你当前处于处,你可以移动到任意处。

跳到 的得分为 。你需要求出到达 处获得的最大总得分。

凭借这一道题,取舍在小猿口算中大杀四方,作为大学生的你决定出手,制裁小学生。

输入格式

第一行输入一个正整数(),表示数组的长度。

第二行输入 个整数,...),表示数组中的元素。

输出格式

输出到达处获得的最大总得分。

样例

输入 #1

4
1 3 1 5

输出 #1

7

输入 #2

5
4 3 1 3 2

输出 #2

16

样例1:一开始跳到 处,然后跳到 处。总得分为 1 * 1 + 2 * 3 = 7 。

样例2:直接跳到 处。总得分为 4 * 4 = 16 。