You are given a 2D integer array items, where items[i] = [factorᵢ, priceᵢ] represents the i-th item. You are also given an integer budget.

There are unlimited copies of each item available for purchase. You may buy any number of copies of any items, as long as the total cost of the purchased copies does not exceed budget.

After buying items, you may receive free copies based on the following rules:

• For each item i that you bought at least one copy of, you receive one free copy of every item j such that j != i and factorᵢ divides factorⱼ (that is, factorⱼ % factorᵢ == 0).
• Buying multiple copies of the same item i does not give additional free copies through item i. The free copies are triggered only by whether you bought item i at least once.
• The same item j can be received multiple times for free if it is triggered by purchases of different item types.

Your goal is to return the maximum total number of item copies you can obtain, counting both the purchased copies and the free copies, while spending at most budget on the purchased items.

In short, buying the first copy of an item type unlocks free items (everything whose factor is a multiple of this item's factor), while any extra copies you buy simply add to your total count without unlocking new free items. You want to plan your purchases to maximize the overall number of copies obtained.

The key observation is that purchases fall into two distinct categories with very different "values":

• The first copy you buy of a particular item type is special: it not only counts as one copy itself, but also unlocks one free copy of every item j whose factor is a multiple of this item's factor. So buying the first copy of item i gives you cnt total copies, where cnt is the number of items j satisfying factorⱼ % factorᵢ == 0 (this count includes item i itself, accounting for the purchased copy plus all the free copies it triggers).
• Every additional copy (whether of the same type or of a new type, but counting only the "extra" purchases beyond the first that unlock bonuses) only adds 1 to the total count per copy bought. It gives no new bonuses.

This naturally splits the budget into two parts:

1. A portion of the budget spent on buying the first copies of selected item types, where each first copy unlocks a bunch of free items. Since each item type can contribute its bonus only once (buying it the first time), and we want to maximize the total number of items gained for a given spent amount, this is exactly a 0-1 knapsack: each item type is either "activated" (bought once, costing priceᵢ and yielding cntᵢ copies) or not. Let f[i] be the maximum number of copies obtainable when spending exactly up to budget i on these first purchases.

2. The remaining budget can be used to buy plain extra copies. Since these copies provide no bonus, the smartest move is to spend the leftover money on the cheapest item available, getting 1 copy per mn units of money, where mn is the minimum price among all items. With a leftover budget of budget - i, this yields ⌊(budget - i) / mn⌋ extra copies.

Putting the two parts together, if we spend i on the first purchases (gaining f[i] copies) and the rest on cheap extras, the total is f[i] + ⌊(budget - i) / mn⌋. By trying every possible split point i and taking the maximum, we arrive at the final answer.

The reason this works cleanly is that there's no harm in treating the leftover as "all spent on the cheapest item": any extra copy we'd otherwise buy could be replaced by the cheapest one for at least as many copies, and any genuine bonus-unlocking purchase is already accounted for inside the knapsack part f.

Pattern Learn more about Greedy and Dynamic Programming patterns.

We implement the idea above using a 0-1 knapsack for the first-copy purchases, then combine it with the cheapest-item filling for the leftover budget.

Step 1: Set up the DP array and track the minimum price.

We create a 1D DP array f of length budget + 1, where f[j] represents the maximum number of copies (purchased first copies plus the free copies they unlock) obtainable while spending at most j on these first purchases. Initially f is all zeros, meaning spending nothing yields nothing.

We also maintain mn, the minimum price among all items, initialized to inf. This will later be used for spending the leftover budget on the cheapest item.

f = [0] * (budget + 1)
mn = inf

Step 2: Process each item type as a knapsack item.

For each item [factor, price]:

• Update the minimum price: mn = min(mn, price).
• Compute cnt, the number of copies gained by buying the first copy of this item. This equals the number of items j whose factor is a multiple of factor, i.e. factor_j % factor == 0. This single sum counts both the purchased copy (when j == i, the divisibility holds trivially) and all the free copies it unlocks.

mn = min(mn, price)
cnt = sum(factor_j % factor == 0 for factor_j, _ in items)

• Run the classic 0-1 knapsack inner loop, iterating the budget j from high to low (budget down to price). Iterating in reverse ensures each item type is used at most once (we never reuse the same item's just-updated state within this pass):

for j in range(budget, price - 1, -1):
    f[j] = max(f[j], f[j - price] + cnt)

Here f[j - price] + cnt means: take the best result using budget j - price, then activate the current item for price, gaining cnt copies.

Step 3: Combine first purchases with leftover spending.

After the DP is filled, f[i] is the best number of copies when budget i is used on first purchases. The remaining budget - i is spent buying the cheapest item, yielding (budget - i) // mn plain copies. We enumerate every split point i and take the maximum:

return max(x + (budget - i) // mn for i, x in enumerate(f))

where x is f[i] and i ranges over all possible budgets 0 to budget.

Complexity analysis.

• Time complexity: O(n² + n × budget). Computing cnt for all items takes O(n²) total, and the knapsack loop takes O(n × budget). The final enumeration is O(budget).
• Space complexity: O(budget) for the DP array f.

The whole approach hinges on the 1D reverse-iteration knapsack pattern to correctly enforce the "buy first copy once" rule, combined with a simple greedy fill of leftover budget using the cheapest item.