\(X := \text{LCM}(A_1, A_2, \dots, A_N)\) を固定すると, \(X\) の約数から重複のないように \(N\) 個選び, 総和を \(X\) とする問題になります.
\(X\) には約数が多い数を選びたいので, \(10^9\) 以下の高度合成数である \(X = 735134400\) を採用してみましょう.

\(X\) の約数を小さい順に \(D = (D_1, D_2, \dots, D_{1344})\) とします.
\(D = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, \dots)\) と小さい数は充実しているので, 大きい数を (ある程度余裕を持たせながら) 貪欲に採用して総和を \(X\) に近づけ, 小さい数で \(X\) に合わせれば良さそうです.

これは, 答えを仮に \(A = (D_1, D_3, \dots, D_{2N - 1})\) として,
\(d = D_{1344}, \dots, D_1\) の順に, \(d\) を \(A\) の最大の要素と交換して総和が \(X\) 以下ならば \(d\) を答えに入れて採用を確定する
といった方法で, \(N ≤ 500\) の制約の元で総和を \(X\) にすることができます.

実装例 (C++)