All problems

Exact Prices in the Tin

Hard · dynamic programming

A market stall keeps its coins in a tin. The tin holds counts[i] coins of value coins[i] pence, for every kind i. A customer who hands over exactly the right money gets no change, so a price can be paid exactly when some selection of coins from the tin adds up to it. Each coin in the tin can be used once.

The stall prices everything at a whole number of pence from 1 to limit.

Return how many of the prices 1, 2, ..., limit can be paid exactly with coins from the tin.

Examples

Example 1

Input: coins = [1, 5], counts = [2, 1], limit = 8

Output: 5

The tin can pay 1, 2, 5, 6 and 7 pence exactly. It cannot pay 3 or 4, and the most it can pay is 7.

Example 2

Input: coins = [3], counts = [3], limit = 10

Output: 3

Only 3, 6 and 9 pence can be paid.

Example 3

Input: coins = [10], counts = [1], limit = 5

Output: 0

The only coin is worth more than every price.

Constraints