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

typedef vector<int> vi;
typedef vector<vi> vvi;

class Solution {
  int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
  }

  vvi gcdab;
  map<int, map<int, int> > dp; // operation, mask
  int all;

  int rec(int op, int mask) {
    // cout << op << " " << bitset<8>(mask) << endl;
    if (mask == all) return 0;
    if (dp[op].contains(mask)) return dp[op][mask];

    vi pos;
    vi idx;
    int bit = 1;
    int ix = 0;
    while (bit <= all) {
      if ((bit&mask)==0) {
        idx.push_back(ix);
        pos.push_back(bit);
      }
      bit <<=1;
      ix++;
    }

    int maxi = 0;
    for (int i = 0; i < pos.size(); i++) {
      for (int j = i + 1; j < pos.size(); j++) {
         maxi = max(maxi, rec(op+1, mask|pos[i]|pos[j]) + gcdab[idx[i]][idx[j]]*op);
      }
    }

    dp[op][mask] = maxi;
    return maxi;

  }

public:
    int maxScore(vector<int>& nums) {
      int speed = []() {ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);return 0;}();
      int n = nums.size();
      all = 1 << n;
      all--;
       gcdab = vvi(n, vi(n)); 
       for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          gcdab[i][j] = gcd(nums[i], nums[j]);
        }
       }

      return rec(1, 0);
    }
};
59793