<p>You are given two integer arrays <code>nums1</code> and <code>nums2</code> of length <code>n</code>.</p>

<p>The <strong>XOR sum</strong> of the two integer arrays is <code>(nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1])</code> (<strong>0-indexed</strong>).</p>

<ul>
	<li>For example, the <strong>XOR sum</strong> of <code>[1,2,3]</code> and <code>[3,2,1]</code> is equal to <code>(1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4</code>.</li>
</ul>

<p>Rearrange the elements of <code>nums2</code> such that the resulting <strong>XOR sum</strong> is <b>minimized</b>.</p>

<p>Return <em>the <strong>XOR sum</strong> after the rearrangement</em>.</p>

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

<pre>
<strong>Input:</strong> nums1 = [1,2], nums2 = [2,3]
<strong>Output:</strong> 2
<b>Explanation:</b> Rearrange <code>nums2</code> so that it becomes <code>[3,2]</code>.
The XOR sum is (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2.</pre>

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

<pre>
<strong>Input:</strong> nums1 = [1,0,3], nums2 = [5,3,4]
<strong>Output:</strong> 8
<b>Explanation:</b> Rearrange <code>nums2</code> so that it becomes <code>[5,4,3]</code>. 
The XOR sum is (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8.
</pre>

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

<ul>
	<li><code>n == nums1.length</code></li>
	<li><code>n == nums2.length</code></li>
	<li><code>1 &lt;= n &lt;= 14</code></li>
	<li><code>0 &lt;= nums1[i], nums2[i] &lt;= 10<sup>7</sup></code></li>
</ul>

# class Solution:
#     def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
        


# from typing import List
# import functools

# class Solution:
#     def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
#         n = len(nums1)
        
#         # Use memoization to store results of subproblems
#         @functools.lru_cache(None)
#         def dp(mask, i):
#             if i == n:
#                 return 0
            
#             min_xor_sum = float('inf')
#             for j in range(n):
                
#                 if mask & (1 << j) == 0:
#                     current_xor_sum = (nums1[i] ^ nums2[j]) + dp(mask | (1 << j), i + 1)
#                     min_xor_sum = min(min_xor_sum, current_xor_sum)
            
#             return min_xor_sum
        
#         return dp(0, 0)


from typing import List, Tuple
import functools

class Solution:
    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        
        @functools.lru_cache(None)
        def dp(used: Tuple[int], i: int) -> int:
            if i == n:
                return 0
            
            min_xor_sum = float('inf')
            used_set = set(used)
            
            for j in range(n):
                if j not in used_set:
                    current_xor_sum = (nums1[i] ^ nums2[j]) + dp(tuple(sorted(used_set | {j})), i + 1)
                    min_xor_sum = min(min_xor_sum, current_xor_sum)
            
            return min_xor_sum
        
        return dp(tuple(), 0)
577