Subsequence sum y GCD

Me encontré con esta pregunta en un desafío de programación hace aproximadamente un mes, pero el editorial no se publicó, así que lo pregunto aquí.

Hay una matriz A de tamaño N. Encuentre la suma * MCD de subsecuencias de longitud K de A.

Ejemplo

Si A = [1, 2, 3] y K = 2,

{1, 2} = 3 (suma) * 1 (MCD) = 3

{1, 3} = 4 (suma) * 1 (MCD) = 4

{2, 3} = 5 (suma) * 1 (MCD) = 5

Ans => 3 + 4 + 5 = 12