EXTENDED-BOTTOM-UP-CUT-ROD (p, n) 1 let r[0..n] and s[0..n] be new arrays 2 r[0] = 0 3 for j=1 to n 4 5 6 7 8 9 9 = - for i = 1 to j if q < p[i] + r[j-i] q = p[i] + r[ji] s[j] = i r[j] = q 10 return and s Store the optimal first piece size for rod length = j Provide clear, concise answers to each of the following related questions. . (10 points). Consider an extension to the rod cutting problem in which every cut incurs a cost, and the cost varies based on where the cut oc- curs. Carefully describe the changes you would make to the algorithm to accommodate this change. Refer to Extended-Bottom-Up-Cut-Rod()