Rod Cutting

Statement

You are given a rod of length n meters. You can cut the rod into smaller pieces, and each piece has a price based on its length. Your task is to earn the maximum revenue that can be obtained by cutting up the rod into smaller pieces.

Let’s say you have a rod of length $4$ meters and you have two lists: one that defines the lengths, and the other that defines the price of each length.

lengths = [1, 3, 4]

prices = [2, 7, 8]

You can cut the rod into the pieces of varying lengths and earn the following revenues:

• Four pieces of length $1$ meter $= 2 + 2 + 2 + 2 = 8$

• One piece of length $1$ meter and another piece of length $3$ meters $= 2 + 7 = 9$

• One single piece of length $4$ meters $= 8$

Therefore, the maximum revenue you can generate by cutting the rod and selling the pieces is $9$, by cutting the rod into two pieces, one of length $1$ and the other of length $3$.

Constraints:

• $1\leq$ n $\leq40000$
• $1\leq$ prices[i] $\leq10^6$
• $1\leq$ lengths[i] $\leq n$
• prices.length $=$ lengths.length

Examples