While walking through the Middle East, you come across the Cave of Forty Thieves. In this cave there are n treasures t$1,$ t$2,...$ tn$,$ which have weights w$1,$ w$2,...,$ wn and values v$1,$ v$2,...,$ vn$.$ Unfortunately, the only sack you carry can carry at most P units of weight before breaking, so you probably won't be able to take all the treasures. Fortunately, you also bring with you a magic knife that allows you to split any treasure that doesn't fit whole in your sack to take just a portion of it$.$ We assume that, when splitting a treasure, it maintains a consistent fraction in terms of its weight and value $($that is$,$ the third part of the treasure ti has weight wi$/3$ and value vi$/3).$ a$)$ Describe a time $\backslash$theta $($n log n$)$ greedy algorithm to maximize the total value of the treasures added to the bag. b$)$ Prove that your algorithm is correct. c$)$ Show how to improve the time to O$($n$)$ using the k$-$selection algorithm.