2398: 切割钻石
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：11
解决：11
题目描述
在一些非常小众的钻石市场上，1 克拉的钻石可以卖 1 万元，但 100 克拉的钻石卖不到 100 万元，这是因为大块钻石鲜有人问津。假设你是一个经销商，请研究一下如何将大钻石切割成小钻石，获得更多的收益。
给定一颗大号钻石，重量为 n 克拉。市场上，各种重量的钻石的价格是非常稳定的，每一颗重量为 i 克拉的钻石，都可以卖出 ai 元。假设切割钻石不会有任何损耗，请问应该如何切割钻石，才能使得售出的总价达到最高呢？
给定一颗大号钻石，重量为 n 克拉。市场上，各种重量的钻石的价格是非常稳定的，每一颗重量为 i 克拉的钻石，都可以卖出 ai 元。假设切割钻石不会有任何损耗，请问应该如何切割钻石，才能使得售出的总价达到最高呢？
输入
第一行：单个整数 n；
第二行：n 个整数，表示 a1 ,a2,⋯,an。
第二行：n 个整数，表示 a1 ,a2,⋯,an。
输出
单个整数：表示切割钻石后可以获得的最大售价之和。
样例输入 复制
7
10 28 39 40 50 60 70样例输出 复制
95提示
样例1解释：
7=2+2+3
95=28+28+39
数据范围：
1≤a1<a2<⋯<an≤100000。
对于 30% 的数据，1≤n≤20；
对于 60% 的数据，1≤n≤200；
对于 100% 的数据，1≤n≤2000。
7=2+2+3
95=28+28+39
数据范围：
1≤a1<a2<⋯<an≤100000。
对于 30% 的数据，1≤n≤20；
对于 60% 的数据，1≤n≤200；
对于 100% 的数据，1≤n≤2000。