题目描述
钻石市场上，$1$ 克拉的钻石可以卖 $1$ 万元，但 $100$ 克拉的钻石卖不到 $100$ 万元，这是因为大块钻石鲜有人问津。假设你是一个经销商，请研究一下如何将大钻石切割成小钻石，获得更多的收益。
给定一颗大号钻石，重量为 $n$ 克拉。市场上，各种重量的钻石的价格是非常稳定的，每一颗重量为 $i$ 克拉的钻石，都可以卖出 $a_i$ 元。假设切割钻石不会有任何损耗，请问应该如何切割钻石，才能使得售出的总价达到最高呢？
输入
第一行：单个整数 $n$；
第二行：$n$ 个整数，表示 $a_1,a_2,\cdots,a_n$。
输出
单个整数：表示切割钻石后可以获得的最大售价之和。
样例输入输出
输入#1
复制
7
10 28 39 40 50 60 70
提示
+ $1\leq a_1< a_2 <\cdots