条形蛋糕

题目描述

寒假到了，小杨同学打算找一份兼职，顺便体验一下打工人的生活。

小杨同学给一家蛋糕店发送了一份自己的简历，希望可以在寒假来这里帮忙。店长最近正好遇到了一个难题：店里每天会做一条长条蛋糕，但是不同长度的蛋糕块卖出的价格不同，应该怎么分才能卖得最多呢？

给定一条长度为 $n$ 的长条蛋糕和一个价格表，该价格表表示长度为 $i$（$1 \le i \le n$）的蛋糕块的价格为 $p_i$。求蛋糕的分割方案，使得总销售价格最大，注意蛋糕块的长度必须为整数。

输入格式

• 第一行一个正整数 $n$，表示长条蛋糕的总长度；
• 第二行 $n$ 个正整数 $p_i$，表示不同长度蛋糕块的价格。

输出格式

一行一个正整数，表示最大总销售价格。

数据范围

$1 \le n \le 1000$，$1 \le p_i \le 10^6$。

样例

输入样例 1

4
1 5 8 9

输出样例 1

10

样例解释

总长度为 4 的长条蛋糕，把蛋糕分成两段长度都为 2 的价格为 5 + 5 = 10，分段价格为最高总销售价格。