Here we consider a version of the PRETTY PRINTING problem. We are given n words w_1, w_2, ..., w_n each having lengths l_1, l_2 ..., l_n (all non-zero integers). We wish to place words on multiple lines of length M, but pay a penalty for the spaces at the end of each line. The penalty for each line will be the number of empty spaces at the end of that line raised to the power of three. The total penalty is the sum of the penalties for each line, including the last line. Our goal is place words on lines (words cannot be reordered) in a way that minimizes the total penalty. Note that the actual words do not matter, just their lengths. Also note that there must be a single space between each word on a line, and the first word starts in the leftmost location. Furthermore, the words must fit on a line - you may assume this is possible, for example Forall i, l_i lessthanorequalto M. For instance, let n = 6, (l_1, l_2, l_3, l_4, l_5, l_6) = (3, 5, 5, 2, 8, 6), and M = 20. If the first four words are on the first line, there are 20 - (3 + 1 + 5 + 1 + 5 + 1+ 2) = 20 - 18 = 2 spaces at the end (penalty 2^3 = 8). The remaining two words go on the next line: there will be 20 - (8 + 1 + 6) = 5 spaces at the end of that line, for a penalty of 5^3 = 125. Total penalty for this placement is 2^3 +5^3 = 133 Define PP[i] as the minimum penalty for placing words w_i, w_i + 1, ..., w_n on lines of length M. Give a recurrence relation for PP. In the recurrence you may want to use the function extra (i, j) = M + 1 - sigma^j_k = i (l_k + 1) which is the number of spaces at the end of a line containing w_i, w_i + 1, ..., w_j