测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 立即查看

A72038. 条形蛋糕

编程题 入门

题目描述

有一条长度为 n 的条形蛋糕。已知长度为 i 的蛋糕可以卖出价格 p_i。你可以把蛋糕切成若干段,每段长度为正整数,切割次数不限。请问这条长度为 n 的蛋糕最多能卖多少钱。

输入格式

第一行一个整数 n

第二行 n 个正整数 p_1,p_2,\ldots,p_n,表示不同长度蛋糕的价格。

输出格式

输出一个整数,表示最大总价格。

输入输出样例

输入 #1
4
1 5 8 9
输出 #1
10
输入 #2
10
1 5 8 9 10 17 17 20 24 30
输出 #2
30

说明/提示

数据范围

1 \le n \le 10^31 \le p_i \le 10^5