class Solution {
public:
    int solve(vector<int>& nums, int ops, int mask,vector<int>& dp){
        int m = nums.size(), n = (m/2);
        if(ops > n)
            return 0;
        if(dp[mask] != -1)
            return dp[mask];
        for(int i = 0 ; i < m; i++){
            if(mask & (1<<i))continue;
            for(int j = i + 1 ; j < m; j++){
                if(mask & (1<<j))continue;
                int newMask = (1<<i) | (1<<j) | mask;
                int score = ops*__gcd(nums[i], nums[j]) + solve(nums, ops+1, newMask, dp);
                dp[mask] = max(dp[mask], score);
            }
        }
        return dp[mask];
    }
    int maxScore(vector<int>& nums) {
        vector<int> dp(1<<14, -1);
        return solve(nums, 1, 0, dp);
    }
};