You are given an n m Hershey's bar. Your goal is to devise an algorithm A that takes as input (n, m) and returns the minimal number of cuts needed to divide the bar into perfect squares of either 1x1, 2x2, 3x3, . . ., jxj. With each cut, you can split the bar either horizontally or vertically. The first cut will split the Hershey's bar into two sub-bars; after that each cut splits one remaining sub-bar into two. For example, A(2, 3) = 2 because 2x3 (2x2, 1x2) (2x2, 1x1, 1x1). 1. Hint: Notice that no matter the rectangle input n m, it is always possible to make a perfect square in the first cut. But this strategy will fail. It is possible to find an example input size for which the strategy of picking the cut which creates the largest square leads to extra cuts in total. 2. You can not have fraction, after each cut, the generated rectangles will have integer dimensions (width and height are integer values). 3. Devise a DP algorithm which determines the minimal number of cuts. 4. If your solution has run-time (n 3 ), your solution is acceptable. Discuss the runtime of your algorithm, and show that run-time is equal or below (n 3 ).