<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 heapq
class Solution:
    def maxScore(self, nums: List[int]) -> int:
        # # in general how does dp work when its removing 2 things from the set at at time 

        # # group then find ordering?

        # @cache
        # def fast_gcd(a, b):
        #     if not b:
        #         return a

        #     return fast_gcd(b, a % b)

        # nums.sort()
        # ignore = set()
        # heap = []

        # for i in range(len(nums) - 1, -1, -1):
        #     if i in ignore:
        #         continue
        #     for j in range(i - 1, -1, -1):
        #         if j in ignore:
        #             continue

        #         if nums[i] % nums[j] == 0:
        #             heapq.heappush(heap, fast_gcd(nums[i], nums[j]))
        #             ignore.add(i)
        #             ignore.add(j)
        #             break

        # for i in range((len(nums) - len(ignore)) // 2):
        #     heapq.heappush(heap, 1)

        # res = 0
        # for i in range(len(heap)):
        #     res += (i + 1) * heapq.heappop(heap)

        # return res

        @cache
        def fast_gcd(a, b):
            if not b:
                return a

            return fast_gcd(b, a % b)

        res = 0
        def perm(i):
            if i >= len(nums):
                heap = []
                for k in range(0, len(nums), 2):
                    heapq.heappush(heap, fast_gcd(nums[k], nums[k + 1]))

                curr = 0
                for i in range(len(heap)):
                    curr += (i + 1) * heapq.heappop(heap)

                nonlocal res
                res = max(res, curr)
                return

            for j in range(i + 1, len(nums)):
                nums[i + 1], nums[j] = nums[j], nums[i + 1]
                perm(i + 2)
                nums[i + 1], nums[j] = nums[j], nums[i + 1]

        perm(0)
        return res
3164