Maximum Cuboid Stack Height With GCD Condition

You are given an array cuboids, where cuboids[i] = [d1, d2, d3] are the dimensions of the i-th cuboid. You may reorient any cuboid: assign its three dimensions to width, length and height in any order.

Build a vertical stack of cuboids. Cuboid i may be placed directly on top of cuboid j if, with the orientations you chose for both, all of the following hold:

• width(i) <= width(j)
• length(i) <= length(j)
• height(i) <= height(j)
• the chosen heights are not coprime: gcd(height(i), height(j)) > 1

Each cuboid may be used at most once. A single cuboid on its own is a valid stack.

Return the maximum possible total height of a stack, where each used cuboid contributes its chosen height.

Examples

Example 1

Input: cuboids = [[4,6,8],[2,3,4]]
Output: 12
Explanation: Orient [4,6,8] with height 8 (base 4 x 6) and place [2,3,4] on it with height 4 (base 2 x 3). All base and height inequalities hold and gcd(4, 8) = 4 > 1, so the total height is 8 + 4 = 12.

Example 2

Input: cuboids = [[3,3,3],[2,2,2]]
Output: 3
Explanation: The small cube fits on the large one dimensionally, but every orientation gives heights 2 and 3, and gcd(2, 3) = 1, so they cannot be stacked. The best stack is the larger cube alone.

Example 3

Input: cuboids = [[5,10,10],[4,4,9]]
Output: 14
Explanation: Orienting [4,4,9] with height 9 maximizes its own height, but gcd(9, 10) = 1 blocks stacking. Choosing height 4 (base 4 x 9) instead allows it on [5,10,10] with height 10 (base 5 x 10), since gcd(4, 10) = 2 > 1: total 10 + 4 = 14, beating either cuboid alone.