You have n items, cost is c(i) and delivery cost is d(i). If customer orders more than one item, then they get it for the minimum delivery cost. How do you find the maximum amount of money you can make after delivering m items? I know this is a knapsack problem, but I just can't find a way to solve it. And I want to make sure I am able to solve these problems for future interviews.

For e.g.
cost and delivery cost respectively (first column being cost, second being delivery cost):
Item 1: 7, 10
Item 2: 4, 15
Item3: 8, 1

m = 2

Input format (java): int n, int m, int[][] arr where n is the total number of items, m is the maximum number of items you can deliver, arr has each row with first element being cost, second being delivery cost.

Output: 31 (You choose the first two items because if you chose the 3rd item, the delivery cost for 2 items would be 1 + 1 (since 1 is the mimimum delivery cost) so you would end up with 23 + 2 = 25.