<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 maxScore(vector<int>& nums) {
        auto f=[](auto& v){
            auto t=v|(v-1);
            v=(t+1)|(((~t&-~t)-1)>>__builtin_ctz(v)+1);
        };
        int n=nums.size(),res=0;
        vector<vector<int>> dp(1<<n);
        // dp[0]={0};
        for(int i=0;i<n;i+=2){
            // printf("%d,",i);
            for(int j=0;j<n;j++){
                for(int k=0;k<j;k++){
                    int x=(1<<j)+(1<<k);
                    int z=gcd(nums[j],nums[k]);
                    if(i==0){
                        dp[x]={z,z};
                        continue;
                    }
                    for(int y=(1<<i)-1;y<1<<n;f(y)){
                        if(x&y) continue;
                        // printf("%d %d %d %d %d;",i,j,k,x,y);
                        // printf("%d ",dp[y].size());
                        // for(auto& x:dp[y]) printf("%d,",x);
                        auto it=ranges::lower_bound(dp[y],z);
                        vector<int> v(begin(dp[y]),it);
                        v.push_back(z);
                        v.insert(end(v),it,end(dp[y]));
                        v.back()=0;
                        for(int j=0;j<=i/2;j++){
                            v.back()+=v[j]*(j+1);
                        }
                        // printf("%d %d,",i,v.size());
                        if(dp[x|y].empty()||dp[x|y].back()<v.back()){
                            dp[x|y]=v;
                        }
                    }
                }
            }
        }
        // for(auto& x:dp.back()) printf("%d ",x);
        return dp.back().back();
    }
};
124553