This problem is an extension of the famous "knapsack problem", but now in 2D and there is no limit on how many apples you can buy. Since there is no limit on the number of apples we can buy, we can simply use 1 array instead of 2 to contain all the dp values. We can show this works because we incorporate the results as we loop through the array. Thus we can "use" the items more than once.

Now after we're done getting the maximum value, we need to find a way to represent it. The simplest way to represent it is to have another array that keeps track of the last item used to get to each element. When we loop through the dp array in the previous paragraph, we can decide to either buy an apple or not to. If we decided buying the apple is the better choice, we can simply change the respective element of the second array to the ID of the apple.

Finally, start from the end (~dp[R][S]~) and backtrack using the second array. Using the second array, we know which apple to buy. Suppose we buy an apple with cost ~j~ and size ~k~, just back to ~dp[R-j][S-k]~, then repeat the process until we can't buy anymore. Make another array to keep track of how many of each apple was used and output the results.

Final Complexity: ~\mathcal O(RSN)~