<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 collections import defaultdict  # defaultdict allows automatic initialization of missing keys

class Solution:
    def maximumANDSum(self, nums, numSlots):
        n = len(nums)  # Number of elements in nums
        # Example: nums = [1, 2, 3], n = 3

        max_numbers_per_slot = 2  # Each slot can hold at most two numbers
        # Reason: Problem constraint ensures each slot can hold up to two numbers

        initial_state = (0,) * numSlots  # Initial state: all slots are empty
        # Diagram: initial_state = (0, 0)
        # All slots are empty: Slot 1: [], Slot 2: []

        dp = defaultdict(int)  # DP table to store max AND sum for each state
        dp[initial_state] = 0  # Initial state with no numbers placed has sum 0
        # Diagram: dp = {(0, 0): 0}
        
        # Iterate over each number in nums to place it in slots
        for num in nums:
            new_dp = defaultdict(int)  # New DP table for current number
            # Example: num = 1

            # Iterate over each state in the current DP table
            for state, current_sum in dp.items():
                # Diagram: state = (0, 0), current_sum = 0
                
                # Iterate over each slot to place the current number
                for slot in range(numSlots):
                    # Check if the slot can hold more numbers
                    if state[slot] < max_numbers_per_slot:
                        new_state = list(state)  # Convert tuple state to list for modification
                        # Reason: Tuples are immutable, so we convert to list to modify
                        new_state[slot] += 1  # Place number in the slot
                        # Diagram: if placing num in slot 1, new_state changes from (0, 0) to (1, 0)
                        new_state = tuple(new_state)  # Convert back to tuple for new state
                        # Reason: Tuples are used as dictionary keys due to their immutability
                        slot_index = slot + 1  # Slot indices are 1-based
                        # Reason: Slot indices start from 1 for AND operation as given in problem

                        # Calculate the new AND sum for the new state
                        new_sum = current_sum + (num & slot_index)
                        # Diagram: current_sum = 0, num = 1, slot_index = 1
                        # new_sum = 0 + (1 & 1) = 1
                        # Reason: Calculate AND operation for num and slot index

                        # Update the new DP table with the maximum AND sum for the new state
                        new_dp[new_state] = max(new_dp[new_state], new_sum)
                        # Diagram: new_dp = {(1, 0): 1}
                        # Reason: Store the maximum AND sum for the new state

            dp = new_dp  # Update the DP table for the next number
            # Diagram after processing num = 1: dp = {(1, 0): 1}
            # Reason: Move to next number, updating dp to new_dp
        
        return max(dp.values())  # Return the maximum AND sum from the DP table
        # Diagram of final DP table: dp = {(2, 1): 5, (1, 2): 4}
        # max(dp.values()) = 5
        # Reason: Final result is the maximum AND sum from all possible states

# 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

17800