Rod Cutting Profit Maximization

Given a rod of length $N$, and an array of prices $P = [P_1, P_2, \dots, P_N]$ where $P_i$ represents the selling price for a rod piece of length $i$, determine the maximum profit obtainable by cutting the rod into one or more pieces. You may choose not to cut the rod at all. The profit is defined as the sum of the prices of the pieces obtained after cutting.

The problem can be formulated using dynamic programming. For a rod of length $N$, let $dp[i]$ denote the maximum profit obtainable for a rod of length $i$. The recurrence relation is given by:

where $dp[0] = 0$. Your task is to compute $dp[N]$ given the rod length and the corresponding prices.

inputFormat

The input is given through stdin and consists of two lines:

1. The first line contains an integer $N$, denoting the length of the rod.
2. The second line contains $N$ space-separated integers. The $i$-th integer represents the price of a rod piece of length $i$.

outputFormat

Output a single integer to stdout representing the maximum profit obtainable from the rod.## sample

4
1 5 8 9

10