<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>

import math
class Solution:
    def maxScore(self, nums: List[int]) -> int:
        aux={}
        nums.sort()
        n=len(nums)
        for i in range(n):
            for j in range(i+1, n):
                x,y = nums[i], nums[j]
                aux[x,y] = math.gcd(x, y)
        
        def evaluate(partition):
            gcds = [aux[min(x,y), max(x,y)] for k,(x,y) in enumerate(partition)]
            gcds.sort()
            score = sum([(i+1)*s for i,s in enumerate(gcds)])
            #print(partition)
            #print(gcds)
            #print(score)
            #print(20*'-')
            return score
        
        partition =[]
        heap=[i for i in range(n)]
        heapify(heap)
        #print(heap)
        used=set()
        curr=None
        ans=0
        def search(i):
            nonlocal partition, curr, ans, used, heap
            #print(heap)
            if i==n:
                ans = max(ans, evaluate(partition))

            elif i<n:
                if curr==None:
                    k = heappop(heap)
                    l=[k]
                    while k in used:
                        k=heappop(heap)
                        l.append(k)
                    
                    curr=nums[k]
                    used.add(k)

                    search(i+1)
                    
                    curr=None
                    used.remove(k)
                    for j in l:
                        heappush(heap, j)

                elif curr!=None:
                    w=curr
                    cands=[k for k in range(n) if k not in used]
                    for k in cands:

                        used.add(k)
                        partition.append([curr, nums[k]])
                        curr = None
                        
                        search(i+1)

                        curr = w
                        used.remove(k)
                        partition.pop()

        search(0)
        return ans 




16500