<p>You are given an integer array <code>nums</code> of length <code>n</code> and an integer <code>numSlots</code> such that <code>2 * numSlots &gt;= n</code>. There are <code>numSlots</code> slots numbered from <code>1</code> to <code>numSlots</code>.</p>

<p>You have to place all <code>n</code> integers into the slots such that each slot contains at <strong>most</strong> two numbers. The <strong>AND sum</strong> of a given placement is the sum of the <strong>bitwise</strong> <code>AND</code> of every number with its respective slot number.</p>

<ul>
	<li>For example, the <strong>AND sum</strong> of placing the numbers <code>[1, 3]</code> into slot <u><code>1</code></u> and <code>[4, 6]</code> into slot <u><code>2</code></u> is equal to <code>(1 AND <u>1</u>) + (3 AND <u>1</u>) + (4 AND <u>2</u>) + (6 AND <u>2</u>) = 1 + 1 + 0 + 2 = 4</code>.</li>
</ul>

<p>Return <em>the maximum possible <strong>AND sum</strong> of </em><code>nums</code><em> given </em><code>numSlots</code><em> slots.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5,6], numSlots = 3
<strong>Output:</strong> 9
<strong>Explanation:</strong> One possible placement is [1, 4] into slot <u>1</u>, [2, 6] into slot <u>2</u>, and [3, 5] into slot <u>3</u>. 
This gives the maximum AND sum of (1 AND <u>1</u>) + (4 AND <u>1</u>) + (2 AND <u>2</u>) + (6 AND <u>2</u>) + (3 AND <u>3</u>) + (5 AND <u>3</u>) = 1 + 0 + 2 + 2 + 3 + 1 = 9.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,10,4,7,1], numSlots = 9
<strong>Output:</strong> 24
<strong>Explanation:</strong> One possible placement is [1, 1] into slot <u>1</u>, [3] into slot <u>3</u>, [4] into slot <u>4</u>, [7] into slot <u>7</u>, and [10] into slot <u>9</u>.
This gives the maximum AND sum of (1 AND <u>1</u>) + (1 AND <u>1</u>) + (3 AND <u>3</u>) + (4 AND <u>4</u>) + (7 AND <u>7</u>) + (10 AND <u>9</u>) = 1 + 1 + 3 + 4 + 7 + 8 = 24.
Note that slots 2, 5, 6, and 8 are empty which is permitted.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= numSlots &lt;= 9</code></li>
	<li><code>1 &lt;= n &lt;= 2 * numSlots</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 15</code></li>
</ul>

from functools import lru_cache


from typing import List
from functools import lru_cache
from typing import List


from typing import List
from typing import List

class SolutionManualCache:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        # Initialize the cache dictionary to memoize results of the dp function
        cache = {}
        
        def dp(index, mask1, mask2):
            # Base case: If all numbers are processed, return 0 (no more AND operations possible)
            if index == len(nums):
                return 0

            # Define the state using the current index and masks
            state = (index, mask1, mask2)
            # If this state has already been computed, return the stored result
            if state in cache:
                return cache[state]

            # Initialize the best result for this state to negative infinity
            maxAndSum = float('-inf')
            # Iterate over each slot to place the current number
            for slot in range(numSlots):
                slotMask = 1 << slot  # Generate mask for the current slot
                # If the slot is available in mask1
                if mask1 & slotMask:
                    # Compute AND sum for placing nums[index] in this slot, update mask1
                    currentAndSum = (nums[index] & (slot + 1)) + dp(index + 1, mask1 ^ slotMask, mask2)
                    # Update the maximum AND sum found so far
                    maxAndSum = max(maxAndSum, currentAndSum)
                # If the slot is available in mask2
                elif mask2 & slotMask:
                    # Compute AND sum for placing nums[index] in this slot, update mask2
                    currentAndSum = (nums[index] & (slot + 1)) + dp(index + 1, mask1, mask2 ^ slotMask)
                    # Update the maximum AND sum found so far
                    maxAndSum = max(maxAndSum, currentAndSum)

            # Cache the best result for this state and return it
            cache[state] = maxAndSum
            return maxAndSum

        # Start the recursive process with all slots available in both masks (1 << numSlots) - 1
        initialMask = (1 << numSlots) - 1
        return dp(0, initialMask, initialMask)

# Example usage:
# sol = Solution()
# print(sol.maximumANDSum([1, 2, 3, 4, 5, 6], 3))  # Output should be 9
# print(sol.maximumANDSum([1, 3, 10, 4, 7, 1], 9))  # Output should be 24

class Solution:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        @lru_cache(None)
        def dp(index, firstSlotMask, secondSlotMask):
            # Base case: if all numbers are processed, return 0
            if index == len(nums):
                return 0

            # Initialize the maximum AND sum to negative infinity to ensure any real sum is larger
            maxAndSum = float('-inf')

            # Iterate over each slot
            for slot in range(numSlots):
                slotIndex = 1 << slot  # Calculate the bitmask for the current slot

                # If the first slot is available for this number
                if firstSlotMask & slotIndex:
                    # Calculate the AND sum if placing the number in this slot and proceed with recursion
                    maxAndSum = max(maxAndSum, (nums[index] & (slot + 1)) + dp(index + 1, firstSlotMask ^ slotIndex, secondSlotMask))
                
                # If the second slot is available for this number
                elif secondSlotMask & slotIndex:
                    # Calculate the AND sum if placing the number in this slot and proceed with recursion
                    maxAndSum = max(maxAndSum, (nums[index] & (slot + 1)) + dp(index + 1, firstSlotMask, secondSlotMask ^ slotIndex))

            # Return the maximum AND sum found for the current recursion level
            return maxAndSum

        # Initial call to the dp function with all slots available in both first and second positions
        return dp(0, (1 << numSlots) - 1, (1 << numSlots) - 1)

# Example usage:
sol = Solution()
nums = [1, 2, 3, 4, 5, 6]
numSlots = 3
print(sol.maximumANDSum(nums, numSlots))  # Output: 9


class SolutionGoodManual:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        # Initialize the cache
        cache = {}
        
        def dp(i, m1, m2):
            if i == len(nums):
                return 0

            # Use a tuple to represent the state
            state = (i, m1, m2)
            if state in cache:
                return cache[state]

            ans = float('-inf')
            for j in range(numSlots):
                if m1 & (1 << j):
                    ans = max(ans, (nums[i] & (j + 1)) + dp(i + 1, m1 ^ (1 << j), m2))
                elif m2 & (1 << j):
                    ans = max(ans, (nums[i] & (j + 1)) + dp(i + 1, m1, m2 ^ (1 << j)))

            # Store the result in the cache
            cache[state] = ans
            return ans

        return dp(0, (1 << numSlots) - 1, (1 << numSlots) - 1)

# Example usage:
sol = Solution()
print(sol.maximumANDSum([1, 2, 3, 4, 5, 6], 3))  # Output: 9
print(sol.maximumANDSum([1, 3, 10, 4, 7, 1], 9))  # Output: 24

class SolutionGood:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        @lru_cache(None)
        def dp(i, m1, m2):
            if i == len(nums):
                return 0

            ans = float('-inf')
            for j in range(numSlots):
                if m1 & (1 << j):
                    ans = max(ans, (nums[i] & (j + 1)) + dp(i + 1, m1 ^ (1 << j), m2))
                elif m2 & (1 << j):
                    ans = max(ans, (nums[i] & (j + 1)) + dp(i + 1, m1, m2 ^ (1 << j)))
            return ans

        return dp(0, (1<<numSlots)-1, (1<<numSlots)-1)


   


class SolutionBadMemGoodTime:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        ans = 0
        for i in range(5000): # guess enough times
            random.shuffle(nums) # try different orders randomly
            cur = 0
            counter = defaultdict(int)
            for n in nums:
                j = 0
                for i in range(1, numSlots+1):
                    if counter[i] < 2 and n & i > n & j: # Greedy
                        j = i
                counter[j] += 1
                cur += n & j
            ans = max(ans, cur)
    
        return ans    

    def maximumANDSum(self, A, ns):
        @lru_cache(None)
        def dp(i, mask):
            res = 0
            if i == len(A): return 0
            for slot in range(1, ns + 1):
                b = 3 ** (slot - 1)
                if mask // b % 3 > 0:
                    res = max(res, (A[i] & slot) + dp(i + 1, mask - b))
            return res
        
        return dp(0, 3 ** ns - 1)


         
class SolutionBadOriginalG:
    def maximumANDSum(self, nums, numSlots):
        n = len(nums)

        # Use memoization to cache results of state computations
        @lru_cache(None)
        def dp(mask):
            count = bin(mask).count('1')
            if count >= n:
                return 0
            
            max_sum = 0
            for slot in range(numSlots):
                for k in range(2):
                    bit_pos = 2 * slot + k
                    if (mask & (1 << bit_pos)) == 0:
                        next_mask = mask | (1 << bit_pos)
                        num = nums[count]
                        and_sum = num & (slot + 1)
                        max_sum = max(max_sum, dp(next_mask) + and_sum)
            return max_sum
        return dp(0)

class SolutionBad:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        @cache
        def dp(i, slm):
            if i >= len(nums):
                return 0
            res = 0
            for s_i in range(numSlots):
                if slm[s_i] == "1" or slm[s_i] == "2":
                    old_slm = slm
                    slm = slm[:s_i] + str(int(slm[s_i]) - 1) + slm[s_i + 1:]
                    res = max(res, (nums[i] & (s_i + 1)) + dp(i + 1, slm))
                    slm = old_slm
            return res
        return dp(0, "2" * numSlots)


        
25900