3946. Maximum Number of Items From Sale I

You are given a 2D integer array items, where items[i] = [factori, pricei] represents the ith 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 such that the total cost of the purchased copies is at most budget.

After buying items, you may receive free copies according to 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 factori divides factorj.
• Buying multiple copies of the same item i does not give additional free copies through item i.
• The same item j can be received multiple times for free if it is received from purchases of different item types.

Return the maximum total number of item copies you can obtain, including both purchased copies and free copies, while spending at most budget on purchased items.

Example 1:

Example 2:

Constraints:

• 1 <= items.length <= 1000
• items[i] = [factori, pricei]
• 1 <= factori, pricei <= 1500
• 1 <= budget <= 1500