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:
i can give you at most one free copy of another item j.i != j and factori divides factorj.(i, j), you can receive a free copy of item j from purchases of item i at most once, regardless of how many copies of item i you buy.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:
Input: items = [[1,6],[2,4],[3,5]], budget = 19
Output: 5
Explanation:
2 * 6 + 4 = 16, which is not greater than budget = 19.factor0 = 1 divides factor1 = 2.factor0 = 1 divides factor2 = 3.Example 2:
Input: items = [[2,8],[1,10],[6,6],[4,12],[5,20],[5,17]], budget = 35
Output: 7
Explanation:
2 * 8 + 10 + 6 = 32, which is not greater than budget = 35.factor0 = 2 divides factor2 = 6.factor0 = 2 divides factor3 = 4.factor1 = 1 divides factor2 = 6.factor2 = 6 does not divide the factor of any other item.Constraints:
1 <= items.length <= 105items[i] = [factori, pricei]1 <= factori <= items.length1 <= pricei <= 1091 <= budget <= 109Loading editor...
[[1,6],[2,4],[3,5]] 19