Problem Statement

Maximum Rod-Cutting Revenue A rod has length `n`. `prices[i]` is the sale price of a piece of length `i`. Cuts are free and pieces may be sold in any combination whose lengths total `n`. Print the maximum revenue. Input The first line contains `n`. The second line contains `n + 1` prices, with the first value (price for length 0) ignored to preserve the source format. Output Print the maximum revenue. Example For `n = 4` and prices `0 2 4 7 7`, the answer is `9` (pieces of lengths 1 and 3).