Rod Cutting Problem

You are given a rod of length (L) and an array of prices of length (L), where the (i)-th element (1-indexed) represents the price of a rod piece of length (i). Your task is to determine the maximum revenue obtainable by cutting the rod into pieces. Specifically, if you denote the maximum revenue for a rod of length (i) as (dp[i]), then the relation is given by:

[ dp[i] = \max_{1 \leq j \leq i} { \text{price}[j-1] + dp[i-j] }, \quad dp[0] = 0 ]

Solve this problem using a dynamic programming approach.

inputFormat

The input is given via standard input (stdin) and consists of two lines. The first line contains a single integer (L), representing the length of the rod. The second line contains (L) space-separated integers, where the (i)-th integer is the price of a rod piece of length (i) (1-indexed).

outputFormat

Output a single integer to standard output (stdout), which is the maximum revenue obtainable by cutting the rod according to the given prices.## sample

8
1 5 8 9 10 17 17 20

22