动态规划?

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

动态规划作为《运筹学》的一个分支,被广泛的用于解决较为复杂的经济管理问题,以达到的最优抉择,获得最大经济收益为目的。也因其多变性,非常的频繁的出现在信息学竞赛的赛场上。

动态规划的核心思想为不断将问题分解为子问题,一直到可以较容易的得到最优答案,再去决定其父问题的决策,因为很大程度的避免了重复子问题的抉择,故可以节约大量时间。

 

现在问题来了,有一个一维数组,存储了n个正整数,下标依次为012.,n-1

现在要从中选取一部分数,你要给出一个选择方案使得你的方案满足下列要求:

  1. 这部分元素的下标应满足stst+5, st+5*2 , st+5*3, … , st+5*x (0 <= st < n ,st <= st+5*x < n)

  2. 在满足第一条要求的方案中,应选取其累加和最大的一种的方案。

Input

 多组输入。

对于每组输入:

第一行输入一个n(1 <= n <= 100000)

接下来的一行有n个整数y(-100000 <= y <= 100000)

Output

 对于每组数据,输出一个整数代表你的方案的累加和。

Sample Input

10
1 2 3 4 5 6 7 8 9 10
3
1 -10 2
3
-1 -2 -3

Sample Output

15
2
-1

Hint

 

Source

zmx