Maximize Profit Under a Bitwise-OR Limit

You are given two integer arrays, profits and masks, both of length n, and an integer limit. The i-th item has a profit of profits[i] and an associated bitmask of masks[i].

You want to select a subset of items such that the bitwise OR of the selected items' masks does not exceed limit:

masks[i_1] | masks[i_2] | ... | masks[i_k] <= limit

If you choose an empty subset, the total profit is 0, and the bitwise OR is defined to be 0.

Return the maximum total profit you can achieve.

Interface

def maxProfitBitwiseOR(profits: list[int], masks: list[int], limit: int) -> int:
    pass

Constraints

• 1 <= n <= 10^5
• profits.length == masks.length == n
• 1 <= profits[i] <= 10^9
• 0 <= masks[i] <= 10^9
• 0 <= limit <= 10^9

Examples

Example 1

Input: profits = [5, 10, 15, 7], masks = [2, 4, 1, 6], limit = 5
Output: 20
Explanation:
- Choosing items at index 0 (`mask = 2`, `profit = 5`) and index 2 (`mask = 1`, `profit = 15`):
  Combined OR is `2 | 1 = 3  5` (invalid).
- If we pick index 1 (`mask = 4`) and index 2 (`mask = 1`), OR is `4 | 1 = 5 <= 5`, total profit is `10 + 15 = 25`.
Wait, profit 25 is achievable with indices 1 and 2!
Hence, the maximum total profit is 25.

Example 2

Input: profits = [10, 20], masks = [8, 12], limit = 7
Output: 0
Explanation:
Both items have masks greater than `limit`. The only valid choice is the empty subset with profit `0`.

Edge Cases

• limit == 0: Only items with mask == 0 can be chosen.
• All items have masks[i] > limit: The best answer is 0 (empty subset).
• Multiple items can be combined greedily because profits are non-negative and the bitwise OR is idempotent.