Flour Orders the Mill Can Fill Exactly

A mill has sealed flour bags in several sizes: there are stock[i] bags of sizes[i] kilograms each. Bags are never opened, so an order of w kilograms can be filled only if some selection of whole bags (each bag used at most once) weighs exactly w. Sizes may repeat in the list.

Return how many whole numbers w with 1 <= w <= cap can be filled.

Examples

Input:  sizes = [3, 5], stock = [2, 1], cap = 20
Output: 5
Explanation: the fillable orders are 3, 5, 6, 8 and 11.

Input:  sizes = [2, 2, 7], stock = [1, 2, 1], cap = 12
Output: 6
Explanation: three 2 kg bags and one 7 kg bag fill 2, 4, 6, 7, 9 and 11 (13 is over the cap).

Constraints

• 0 <= len(sizes) == len(stock) <= 100
• 1 <= sizes[i] <= 10**4, 1 <= stock[i] <= 10**4
• 1 <= cap <= 10**6
• Adding the bags one at a time can mean a million separate updates; that is too slow.

Goals

• Store the set of reachable totals as the bits of one Python integer
• Add an item to every reachable total at once with a shift and an OR
• Replace c copies of an item by about log2(c) bundles without losing any total