You have a collection of boxes and want to pack them in your attic. Every box 1' has a width 111;, a height hi, and contains items of total value 11,-. Your attic has the shape. of a right angled isosceles triangle. with two sides of length H. You want to stack the boxes and place them in the attic. You mayr choose the order in which to stack the boxes but you are not allowed to rotate them and you cannot place two boxes side by side. However, not all boxes can t 1n the attic. In order for a box to t its width must be at most H minus its height and the heights of all the boxes below it in the stack. Figure 1 illustrates how boxes are packed to t 1n the atc. Your goal 1s to maximize the value ofthe boxes placed 1n the attic. Figure 1: How boxes are stacked and placed in the attic. Input: A set of n. boxes with box 1': having width 111.. height hi, and value 11;, the height of the attic H , where all heights his and H are integers. Your goal is to maximize the value of the boxes placed in the atc. {a} Assuming all boxes have the same height h. = 1., give an efcient algorithm to nd the optimal arrangement of boxes in the attic. Prove the correctness of your algorithm and analyze its mntirne. (b) For the general case where all boxes have arbitrary integer heights, give an O(nlogn + nH) algorithm to find the optimal arrangement of boxes in the attic.(c) Prove the correctness of your algorithm from part (b) and analyze its runtime