n kinds of goods; an item of kind i costs prices[i]. You must buy exactly wanted[i] items of kind i, no more and no fewer, even if extra items would make the purchase cheaper.
Besides single items, the shop offers bundles bundles. Bundle bundles[i] is an array of length n + 1: bundles[i][j] is how many items of kind j it contains, and the last number is the bundle's price. Any bundle can be bought as many times as you like.
Return the minimum amount you need to pay for the required basket.prices=[3, 4], bundles=[[2, 1, 8], [0, 3, 10]], wanted=[2, 3] → 16
Buying piece by piece costs 2·3 + 3·4 = 18. You can take the first bundle for 8 plus two items of the second kind for 8, or the second bundle for 10 plus two items of the first kind for 6, either way 16. Taking both bundles is not allowed: it gives more of the first kind than needed.
prices=[1, 1], bundles=[[1, 1, 5]], wanted=[1, 1] → 2
The bundle costs more than the same items bought one by one, so paying 2 is better.
prices=[5], bundles=[[2, 7]], wanted=[5] → 19
A bundle can be taken several times: two bundles for 14 give 4 items, and the fifth one is bought for 5. Total 19.
n == prices.length == wanted.lengthn ≤ 6prices[i] ≤ 100wanted[i] ≤ 10bundles.length ≤ 100bundles[i].length == n + 1bundles[i][j] ≤ 50 for j < n; the bundle price bundles[i][n] is between 0 and 1000prices=[3, 4], bundles=[[2, 1, 8], [0, 3, 10]], wanted=[2, 3]
16
Run checks the first 3 tests in your browser. Submit checks all 82 tests on the server, hidden ones included.