You run a plant that produces sheets of aluminum alloy, and then you cut them to size for customers.

Your machine produces rectangular sheets of dimension $QR,$ and you can cut any sheet into two

smaller sheets by making a vertical or horizontal cut at an integer location. So for example, if you

have a $24$ sized piece, you have the following options that you could produce from a single cut:

Two $14$ pieces $($from a horizontal cut at position $1).$

Two $22$ pieces $($from a vertical cut at position $2).$

A $12$ and a $23$ piece $($from a vertical cut at position $1).$

Say you decide to make the cut that produces a $12$ and a $23$ piece. You could then subsequently

cut the $12$ into two $11$ pieces, and the $23$ piece into a $21$ piece and a $22$ piece, and so on$.$

Or you could stop cutting and sell a piece that you've created.

You can also rotate pieces $($so a $23$ piece is the same as a $32$ piece$).$

Suppose you produce $n$ different sized products, where product i has dimensions $x_i{y}_i,$ and you

can sell product i for $v_i$ dollars. $($For examples, perhaps product $1$ is a $22$ piece that you can sell

for $$2,$ and product $2$ is a $35$ piece that you can sell for $$3$ dollars.$)$ You can sell multiple copies

of the ith product if you can produce multiple pieces of that size from your original sheet. Assume

$Q,R,x_i,y_i,$ and $v_i$ for iin$\{1,2,$dots,$n\}$ are positive integers. You will design an algorithm that figures

out your maximum profit among any possible sequence of horizontal$/$vertical cuts.

$($a$)$ Provide pseudocode for a dynamic programming algorithm that outputs your maximum profit.

$($Note: your code doesn't have to output how you should actually divide the piece, just the

profit.$)$ The input to your algorithm should be $(Q,R,x,y,v)$ where $Q$ and $R$ are the size of the

piece, array $x$ contains the values $x_i,$ array $y$ contains the values $y_i,$ and the array $v$ contains the

values $v_i.$

$($b$)$ Explain why your algorithm is correct. $($You don't need to write a full proof, but you should

describe the logic behind the recurrences that you developed to create your algorithm and explain

how your algorithm checks the appropriate cases.$)$

$($c$)$ What is the runtime of your algorithm in terms of $Q,R,$ and $n?$

$($d$)$ Explain briefly how you would modify your algorithm to tell you whether you should divide the

current sheet, and if so$,$ where you should make the cut.