2. While walking on a beach, one day you found a treasure trove. The trove contains n treasures with weights w₁, . . . , w_n and values v₁, . . . , v_n. Unfortunately you have a knapsack that only holds a total weight M. Fortunately there is a knife handy so that you can cut treasures if necessary; a cut treasures retains its frictional value (so, for example, a third of treasure i has weight w_i / 3 and value v_i / 3).

- Describe a (n log n) time greedy algorithm to solve this problem.

- Prove that your algorithm works correctly.

- Improve the running time of your algorithm to (n).