【GESP26年6月6级T1】条形蛋糕

题目描述

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

输入格式

第一行一个正整数 N（1 ≤ N ≤ 1000），表示长条蛋糕的总长度。

第二行 N 个正整数 p_i（1 ≤ p_i ≤ 10000），表示不同长度蛋糕块的价格。

输出格式

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

样例

输入样例 1

4
1 5 8 9

输出样例 1

10

输入样例 2

10
1 5 8 9 10 17 17 20 24 30

输出样例 2

30

数据范围

1 ≤ N ≤ 1000，1 ≤ p_i ≤ 10000。