You are given an integer budget and a $2$D 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 $1$ free copy of an item j (where j $\neq$ i) if $ ext{factor}_i$ divides $ ext{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 \leq$ items.length $\leq 10^5$

• items[i] $= [ ext{factor}_i, ext{price}_i]$

• $1 \leq ext{factor}_i \leq$ items.length

• $1 \leq ext{price}_i \leq 10^9$

• $1 \leq$ budget $\leq 10^9$

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.