You are given an integer budget and a 2D integer array items, where items[i] = [factor_i, price_i] represents the factor and price of item i.

You can purchase any number of copies of each item as long as the total cost of all purchased items does not exceed budget.

For each purchased copy of item i, you receive one free copy of an item j (where j ≠ i) if factor_i divides factor_j. If no such item j exists, you do not receive a free copy for that purchased item.

Return the maximum total number of items, including both purchased and free copies, that you can obtain.

Constraints:

• $1 ≤$ items.length $≤ 10⁵$

• items[i] = [factor_i, price_i]

• $1 ≤$ factor_i $≤$ items.length

• $1 ≤$ price_i $≤ 10⁹$

• $1 ≤$ budget $≤ 10⁹$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.