26. Consider the following optimization problem. Alex is a wizard and he wants to cast spells to grow the height of a tower. Alex has n types of spells, denoted by $(a_i, b_i, k_i)$ for $1 \le i \le n$, where $a_i, b_i \ge 1$.

If Alex casts the $i^{th}$-type of spell in the beginning of a round, the height of the tower grows by $a_i$ immediately. Then, when it comes to the end of each round for the next $k_i$ rounds, including the round Alex casts the spell, the height of the tower shrinks by $b_i$.

The effect of the spells can stack. So, at the end of each round, the height the tower shrinks is equal to the sum of $b_i$ for all spell i that is still in effect.

Alex can cast at most one spell in each round, and each spell can be cast at most once. Alex can choose any subset of spells he wants and cast them in any order he likes. The tower starts at height zero. The problem is to compute the maximum record height of the tower that Alex can make.

(a) (2%) Suppose that n = 4 and the spells are (5,3,2), (10,9,2), (20,33,1), and (30,115,1). What is the maximum record height of the tower Alex can make?

(b) (3%) Define the following notions. For any $1 \le i,j \le n$,

• Let $A(i,j)$ denote the maximum record height of the tower, if (i) only the first i spells are considered and (ii) j spells are in effect when the value $A(i,j)$ is attained.
• Let $B(i,j)$ denote the maximum record height of the tower, if (i) only the first i spells are considered, (ii) j spells, including the $i^{th}$ spell, are in effect when the value $B(i,j)$ is attained, and (iii) the $i^{th}$ spell is cast at the first round.

$A(i,j)$ and $B(i,j)$ are defined to be $-\infty$ if it is not possible. Based on the optimal substructure, write down the recurrence formula for $A(i,j)$ and $B(i,j)$, as is done in Question 25-(b). If needed, you may state explicitly and assume that $(a_i,b_i,k_i)$ are sorted in a particular order.