Maximize revenue from inventory sales

Problem

A store has n different products. For each product i (0-indexed), you are given an integer quantity[i] representing how many units of that product are currently in stock.

The store will serve m customers. Each customer buys exactly one unit of some product, subject to availability (you cannot sell a product whose stock is 0).

Pricing rule:

• When a customer buys one unit of product i , the price they pay is equal to the current remaining stock of product i before the purchase.
• After the purchase, the stock of product i decreases by 1 (i.e., quantity[i]-- ).
• Thus, if product i has stock 5 when a customer arrives and they buy it, that customer pays 5, and the stock becomes 4 for future customers.

The store can choose, for each customer, which product to sell (among those with positive stock) in order to maximize total revenue.

If m is larger than the total number of units in stock, then at most the total stock many customers can be served; the remaining customers simply cannot buy anything.

Input

• An integer n – the number of different products.
• An array quantity of length n , where quantity[i] is a non-negative integer representing the initial stock of product i .
• An integer m – the number of customers, where each customer buys at most one unit as described.

Output

Return a single integer: the maximum total revenue the store can obtain by appropriately choosing which product to sell to each customer.

You should design an efficient algorithm suitable for large n, m, and quantities.

Example

Suppose:

• n = 2
• quantity = [2, 3]
• m = 3

One optimal sequence of sales is:

• Customer 1 buys from product 1 (stock 3) → pays 3, stock becomes [2, 2] .
• Customer 2 buys from product 0 (stock 2) → pays 2, stock becomes [1, 2] .
• Customer 3 buys from product 1 (stock 2) → pays 2, stock becomes [1, 1] .

Total revenue = 3 + 2 + 2 = 7, which is optimal.

Implement a function that computes this maximum revenue.