Given a rod of length n inches and an array of prices price[] that contains prices of all pieces of size smaller than n. Write a program to determine the maximum revenue obtainable by cutting up the rod and selling the pieces.

Problem Note

• You can perform these cuts in any order.
• After a cut, the rod gets divided into two smaller sub-rods.
• Two different sequences of cuts may give maximum revenue.

Example 1

If length of the rod and the prices of different pieces are given
Input: n = 8, price[] = [1, 5, 8, 9, 10, 17, 17, 20]

length | 1   2   3   4   5   6   7   8  
---------------------------------------
price  | 1   5   8   9  10  17  17  20

Output: 22
Explanation: The maximum obtainable revenue is 22.(By cutting the rod in two pieces of lengths 2 and 6)

Example 2

Input: n = 8, price[] = [3, 5, 8, 9, 10, 17, 17, 20]

length | 1   2   3   4   5   6   7   8 
-------------------------------------- 
price  | 3   5   8   9  10  17  17  20

Output: 24
Explanation: The maximum obtainable revenue is 24.(By cutting the rod in eight pieces of lengths 1)