The castle is represented by a 2D grid (see the figure below for an example) of size m \times n rooms. You can only move to a neighboring room and in one direction at a time: either down from one row to the next (i direction), or to the right from one column to the next (j direction). In other words, from room (i, j) you can only move either to room (i+1, j) or to room (i, j+1). In every room (i, j) there are a number of elves, indicated by E[i, j], and each of them gives you as many rings as there are elves in that room, but there are also a number of hideous orcs, indicated by O[i, j], and each of them will take from you up to as many rings as there are orcs in that room, possibly including rings you collected from prior rooms. You cannot have a negative ring count, but it is conceivable that you end up without any rings (for instance, if there are 3 elves and 2 orcs, overall the elves give you 9 rings and the orcs take from you 4 rings, but if there are 4 orcs, they will try and take up to 16 rings). Starting at the castle entrance in room (1, 1), you must proceed to room (m, n) where a fabled golden griffin is waiting to take you to safety, and you must collect as many rings as possible (if any at all) along the way. (1,1) (m,n) By applying what you've learned in TCSS 343, that is, stating this problem formally and finding a self-reduction to solve it, you are able to write an algorithm to help you traverse the castle and win the game. Suppose then that you are given the following instance of the problem above: m=n=3 (in other words, exactly the example in the figure itself), and room (i, j) contains E[i,j]=2i+j elves and O[i,j]=i+j orcs ifj is even, but E[i,j]=i+j elves and O[ij]=2i+j orcs if jis odd. In that case, the maximum final number of rings you can collect in the castle is (fill in the blank with the number). Now writing R for a move to the right, that is, from room (i, j) to room (i, j+1), and writing D form a move down, that is, from room (i, j) to room (i+1, j), the path that attains this number consists of the moves However, the number of rings you end up with is not the maximum number of rings you may have gathered during the game, since the orcs take back some when you move from one room to the next. The absolute maximum number of rings reached along the optimal path is, in fact