6218 - 条形蛋糕
题目描述
有一条长度为 n 的条形蛋糕。已知长度为 i 的蛋糕可以卖出价格 p_i。你可以把蛋糕切成若干段，每段长度为正整数，切割次数不限。请问这条长度为 n 的蛋糕最多能卖多少钱。
输入
第一行一个整数 n。
第二行 n 个正整数 p_1,p_2,\ldots,p_n，表示不同长度蛋糕的价格。
输出
输出一个整数，表示最大总价格。
样例
输入
4 1 5 8 9
输出
10
输入
10 1 5 8 9 10 17 17 20 24 30
输出
30
说明
数据范围
1 \le n \le 10^3，1 \le p_i \le 10^5。
标签
