You are given an array of N integers (N is even), at each round you have to select 2 numbers $$$(A[i],A[j])$$$, and do $$$ Sum = Sum + GCD(A[i], A[j]) * round $$$, post calculating sum remove those 2 numbers from Array. What is the maximum possible sum you can obtain?

Round's value starts from 1.

Constraints

$$$ 2 \leq N \leq 20 $$$

$$$ 1 \leq A[i] \leq 1e9 $$$

I tried Bitmasking Dp ( $$$ O(2 ^N * N ^2) $$$ ) but got TLE.

Example :

2 3 5 9

1st Round — 2 5, Sum = GCD(2,5) * 1

2nd Round — 3 9, Sum = GCD(3,9) * 2

The maximum possible sum is 7

Any insights?