<p>You are given <code>nums</code>, an array of positive integers of size <code>2 * n</code>. You must perform <code>n</code> operations on this array.</p>

<p>In the <code>i<sup>th</sup></code> operation <strong>(1-indexed)</strong>, you will:</p>

<ul>
	<li>Choose two elements, <code>x</code> and <code>y</code>.</li>
	<li>Receive a score of <code>i * gcd(x, y)</code>.</li>
	<li>Remove <code>x</code> and <code>y</code> from <code>nums</code>.</li>
</ul>

<p>Return <em>the maximum score you can receive after performing </em><code>n</code><em> operations.</em></p>

<p>The function <code>gcd(x, y)</code> is the greatest common divisor of <code>x</code> and <code>y</code>.</p>

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

<pre>
<strong>Input:</strong> nums = [1,2]
<strong>Output:</strong> 1
<strong>Explanation:</strong>&nbsp;The optimal choice of operations is:
(1 * gcd(1, 2)) = 1
</pre>

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

<pre>
<strong>Input:</strong> nums = [3,4,6,8]
<strong>Output:</strong> 11
<strong>Explanation:</strong>&nbsp;The optimal choice of operations is:
(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11
</pre>

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

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5,6]
<strong>Output:</strong> 14
<strong>Explanation:</strong>&nbsp;The optimal choice of operations is:
(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14
</pre>

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

<ul>
	<li><code>1 &lt;= n &lt;= 7</code></li>
	<li><code>nums.length == 2 * n</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        # The length of the nums list.
        length = len(nums)
      
        # Dynamic programming array to keep track of maximum scores.
        # The index will represent the state of which numbers have been paired.
        dp = [0] * (1 << length)
      
        # Pre-calculate the gcd for all pairs and store them for reuse.
        gcd_pairs = [[0] * length for _ in range(length)]
        for i in range(length):
            for j in range(i + 1, length):
                gcd_pairs[i][j] = gcd(nums[i], nums[j])
      
        # Iterate through all possible states of pairs.
        for state in range(1 << length):
            # Count bits to determine how many numbers have been paired up.
            pairs_count = bin(state).count("1")
            # Continue only if pairs_count is even, since we can only pair up numbers if there's an even count.
            if pairs_count % 2 == 0:
                # Test all available pairs in the current state.
                for i in range(length):
                    if state & (1 << i):
                        for j in range(i + 1, length):
                            if state & (1 << j):
                                # Form next state by removing a pair at indices i and j.
                                next_state = state ^ (1 << i) ^ (1 << j)
                                # Calculate the score for this pair at this count
                                pair_score = (pairs_count // 2) * gcd_pairs[i][j]
                                # Update the max score if this pairing leads to a better score.
                                # The score is the sum of the score for the previous state and
                                # pair_score for the current operation.
                                dp[state] = max(dp[state], dp[next_state] + pair_score)
      
        # Return max score, which is stored at the last index of the dp array.
        return dp[-1]
        
445