Will rate instantly. Please answer fast $(25$ pts$)$ The GEOMETRIC$-$KNAPSACK problem is a variant of the Knapmark problem in which our knapsack is a $2$ D rectangle and the weight constraint is replaced by a packing, constraint, as follows. The input is a set of n items I$=\{$x$\_1,...,$ x$\_$n$\}$ where each item x$\_1$ has a value x$\_$i$$ v$,$ a height x$\_$i$$ h and a width x$\_$i$,$ w$,$ and a rectangle R$=[0,$ W$]\backslash$times $[0,$ H$]$ representing your knapsack. $($The instance can then be represented by the triple $($I$,$ W$,$ H$).)$ We wish to choose a subset of items I$^\text{'}$ I such that. I$^\text{'}$ can be packed into the knapsack while maximizing $\_$x$\_4^*$ x$\_$i v$.($a$)$ Formulate the decision version of GEOMETRIC$-$KNAPSACK. $($b$)$ Is the problem in NP$?$ Justify. You can assume that, given two rectangles in R$^2$ we can decide whether their interior intersect in O$(1)$ time. $($c$)$ Prove that GEOMETRIC$-$KNAPSACK is NP$-$hard by reducing from an NP$-$complete problem. $($Hint: there are multiple options here: You may want to reduce from SUBSET$-$SUM, $0-1$ KNAPSACK or RECTANGLE$-$PACKING. Recall that you need to show the reduction which is a poly$-$time algorithm that convert an instance into the other, and you must show both sides of the correctness.$)$