题目背景

罗三鸡同学遗传了他父母的金融行业属性，从小就非常财迷（因此绰号来金），忽然有一天他迷恋上了卖东西赚钱。

题目描述

这一天三鸡妈妈给了他一根长度为 n 厘米的辣条，他感觉自己吃不完，但是家里其他人又不爱吃，于是他灵机一动，想卖辣条给班上同学赚点零花钱，于是他决定把辣条切割为若干小段，不同长度的小段价格也都不一样，经过全家的精确分析，仔细研究，开会讨论，得出了市场上长为 i 厘米(1<=i<=n)小段的辣条得价格 ai，财迷的罗三鸡想算清楚将 n 厘米的辣条分成整数小段后所能卖到的最大价格。但是怎们算都算不出来，聪明的同学们，请帮助可怜的三鸡计算下吧。

输入格式

第 1 行，一个整数 n（1<=n<=1000）。

第 2 行，n 个空格隔开的整数 (0<=ai<=1000)。

输出格式

一个整数，表示最大价格。

输入输出样例

10
1 5 8 9 10 17 17 20 24 25

27

20
232 206 741 369 293 930 750 415 220 252 871 944 287 242 732 84 946 483 403 995

4910

7
554 737 632 1000 627 976 454

3878