A liquidator is running a one-day clearance sale and must ship out exactly orders units by the end of the day — no more and no fewer. The warehouse holds n distinct product listings; listing i sells for price[i] per unit and has stock[i] units on the shelf. The liquidator may sell any whole number of units from each listing, from 0 up to that listing's stock[i], and the quantities sold across all listings must add up to exactly orders. Determine the maximum total revenue achievable. It is guaranteed that the total stock across all listings is at least orders, so fulfilling the quota is always possible.
The first line contains a single integer n. The second line contains n space-separated integers price[0], ..., price[n-1]. The third line contains n space-separated integers stock[0], ..., stock[n-1]. The fourth line contains a single integer orders.
Print a single integer: the maximum total revenue obtainable while selling exactly orders units in total.
1 <= n <= 10^5 1 <= price[i] <= 10^5 1 <= stock[i] <= 10^5 1 <= orders <= sum(stock[i])
Example 1
Input
3 5 3 8 2 4 1 3
Expected
18
Explanation
There are 3 listings with (price, stock) pairs (5,2), (3,4), (8,1). To sell exactly 3 units at maximum revenue, sell from the highest price first: the price-8 listing has only 1 unit in stock, so sell that unit (revenue 8, 2 units still needed); the next-highest price is 5, with 2 units in stock, so sell both (revenue +10, quota met). Total revenue = 8 + 10 = 18; the cheaper price-3 listing is never touched.
Example 2
Input
2 10 10 3 2 4
Expected
40
Explanation
Both listings are priced at 10, with stocks 3 and 2 (5 units total). To sell exactly 4 units, take stock from either listing until the quota is reached — for instance 3 units from the first listing and 1 from the second (any split of 4 units works identically since the price is the same). Revenue = 4 x 10 = 40.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →