Consider the following Trick-or-Treat problem. You live on a street with n houses. You have a bag to carry your Halloween candy, but your bag can carry at most K ounces of candy. You are given for each house i, an integer weight integer w_i (in ounces) of the candy that the people in house i are handing out. Each house gives out one piece of candy. You can visit each house at most once. Your problem is to collect the largest number of pieces of candy from the n houses without exceeding the capacity of your bag.

Now consider the following greedy algorithm. Sort the houses according to the weight of the candy they are providing. Collect candy from the houses starting from the house that provides the lightest candy, then the next lightest, ... until your bag is full.

Prove by induction that this greedy strategy results in an optimum solution to the Trick-or-Treat problem described above.