Most Copies from a Sale with Divisibility Gifts

# Most Copies from a Sale with Divisibility Gifts You are given item types `items`, where `items[i] = [factor, price]`, and an integer `budget`. Unlimited copies of each type are available. You may buy copies whose total price is at most `budget`. After the purchases, each type `i` that you bought at least once gives one free copy of every other type `j` for which `factor[i]` divides `factor[j]`. The promotion follows these rules: - Buying extra copies of type `i` does not repeat the gifts from that type. - A type cannot give a gift to itself. - Purchases of different types may each give a free copy of the same recipient type; all those copies count. - A free copy is not a purchase and does not trigger gifts. Return the maximum total number of copies you can obtain, counting both purchases and gifts. ### Function `int maximumSaleItems(vector<vector<int>>& items, int budget)` ### Example 1 **Input:** `items = [[2, 3], [3, 2], [6, 4]], budget = 5` **Output:** `4` **Explanation:** Buy one copy each of types `0` and `1`, spending `3 + 2 = 5`. Each gives one free copy of type `2`, since both `2` and `3` divide `6`. You receive two purchased copies and two gifts. Spending the budget on repeated copies of type `1` instead would give only two purchased copies and one gift. ### Example 2 **Input:** `items = [[1, 2], [2, 5], [4, 5]], budget = 6` **Output:** `5` **Explanation:** Buy three copies of type `0` for `6`. Its promotion gives one copy each of types `1` and `2`, for a total of `3 + 2 = 5`. Those gifts are awarded once, not once per purchased copy. Buying type `0` together with either other type would cost at least `7`. ### Constraints - `1 <= items.length <= 1000` - Each `items[i]` contains exactly `[factor[i], price[i]]`. - `1 <= factor[i], price[i] <= 1500` - `1 <= budget <= 1500` ### Clarifications - Types are distinguished by their indices. Equal factors or equal rows do not merge types. - Equal positive factors divide one another, so purchases of such different types can give gifts to each other. - Gifts still count if their recipient type was also purchased. - You may leave money unspent or buy nothing. ### What a Strong Answer Covers - Separating gifts from purchased copies and applying each purchased type's promotion once. - Counting overlapping gifts from different types without treating them as a single copy. - Maximizing the total under the budget, including repeated purchases and unaffordable types.