Problem Description

Winter vacation has arrived, and student Xiao Yang plans to find a part-time job and experience what working life is like.

Xiao Yang sent a resume to a cake shop, hoping to help there during the winter vacation. The shop owner has recently run into a problem: the shop makes one long bar-shaped cake every day, but cake pieces of different lengths sell for different prices. How should the cake be cut to earn the most money?

Interestingly, the owner once studied computer science. Recently, he has become very interested in dynamic programming, so he decided to use this problem to test Xiao Yang. The problem is as follows:

• Given a bar cake of length $n$ and a price list, where the price of a cake piece of length $i$ ($i = 1, 2, \dots, n$) is $p_i$, find a cutting plan that maximizes the total selling price. Note that the length of each cake piece must be an integer.

Input Format

The first line contains a positive integer $n$ ($1 \le n \le 10^3$), representing the total length of the bar cake.

The second line contains $n$ positive integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 10^5$), representing the prices of cake pieces of different lengths.

Output Format

Output one positive integer in one line, representing the maximum total selling price.

4
1 5 8 9

10

10
1 5 8 9 10 17 17 20 24 30

30

Hint

Sample Explanation

In the first sample, a cake of length $1$ is worth $1$, length $2$ is worth $5$, length $3$ is worth $8$, and length $4$ is worth $9$.

For a bar cake with total length $4$, there are five essentially different cutting methods: $\{4\}$, $\{1, 3\}$, $\{2, 2\}$, $\{1, 1, 2\}$, $\{1, 1, 1, 1\}$.

Their corresponding total selling prices are $9, 9, 10, 7, 4$, so the maximum total selling price is $10$.

In the second sample, for a bar cake of length $10$, the cutting method with the maximum selling price is $\{10\}$, and the maximum total selling price is $30$.

Translated by ChatGPT 5