1155. Rod Cutting Problem

A rod of length n can be cut into integer-length pieces, where prices[i] is the price of a piece of length i+1. Return the maximum total price obtainable by cutting the rod (length equals the size of prices). The input is JSON {prices}.

Input: JSON {prices}.

Output: Integer — the maximum obtainable price.

Examples

Input: {"prices":[1,5,8,9,10,17,17,20]}
Output: 22
Explanation: Cut into pieces of length 2 and 6.

Input: {"prices":[2]}
Output: 2
Explanation: Length-1 rod.

Input: {"prices":[3,5]}
Output: 6
Explanation: Two length-1 pieces beat one length-2.

Constraints

• 1<=n<=1000

Asked by