It can be greedily solved as follows.

• Inspect each item in ascending order of the prices. If a coupon is available, use the one with the largest \(D_i\) to buy the item; otherwise, buy it for the regular price.

This greedy algorithm can be implemented with a priority queue etc. and runs in a total of \(\mathrm{O}((N+M)\log M)\) time.

This greedy algorithm is valid because we ultimately need to maximize the sum of \(D_i\) of the coupon used, and those coupons used in an optimal solution can be used however early as long as applicable.