题目背景

钻石市场上，1 克拉的钻石可以卖 1 万元，但 100 克拉的钻石卖不到 100 万元，这是因为大块钻石鲜有人问津。假设你是一个经销商，请研究一下如何将大钻石切割成小钻石，获得更多的收益。

题目描述

给定一颗大号钻石，重量为 n 克拉。市场上，各种重量的钻石的价格是非常稳定的，每一颗重量为 i 克拉的钻石，都可以卖出 ai元。假设切割钻石不会有任何损耗，请问应该如何切割钻石，才能使得售出的总价达到最高呢？

输入格式

第一行：单个整数 n；
第二行：n 个整数，表示 a1,a2,...,an。

输出格式

单个整数：表示切割钻石后可以获得的最大售价之和。

数据范围

1≤a1<a2<...<an≤100000。

对于 30% 的数据，1≤n≤20；

对于 60% 的数据，1≤n≤200；

对于 100% 的数据，1≤n≤2000。

样例数据

输入:

7

10 28 39 40 50 60 70

输出:

95

说明:

7=2+2+3

95=28+28+39