该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

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

题目描述

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

输入格式

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

输出格式

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

7
10 28 39 40 50 60 70

95

样例解释

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。