<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 {
public:
    int n;
    vector<int> base;
    vector<vector<int>> dp;
    int maxScore(vector<int>& nums) {
        base = nums;
        n = base.size();
        dp = vector<vector<int>>(n, vector<int>(pow(2,n)+1,0));
        for (int i = 0; i < n; i++){
            for (int j = i+1; j < n; j++){
                dp[0][0 | (1<<i) | (1<<j)] = __gcd(base[i],base[j]);
            }
        }
        for (int i = 0; i < n-2; i += 2){
            for (int j = 0; j < pow(2,n); j++){
                if (dp[i][j] == 0) continue;
                vector<int> v;
                int num = j;
                for (int i = 0; i < n; i++){
                    if (num%2==0) v.push_back(i);
                    num >>= 1;
                }
                for (int a = 0; a < v.size(); a++){
                    for (int b = a+1; b < v.size(); b++){
                        // cout << dp[i][j] << " " << __gcd(base[v[a]],base[v[b]]) << "\n";
                        dp[i+2][j | (1<<v[a]) | (1<<v[b])] = max(dp[i+2][j | (1<<v[a]) | (1<<v[b])], dp[i][j] + (i+4)/2 * __gcd(base[v[a]],base[v[b]]));
                    }
                }
            }
            // break;
        }
        return dp[n-2][pow(2,n)-1];
    }
};
51698