kotori和素因子

import collections
class Solution():
    def __init__(self, alist, n):
        self.alist = alist
        self.n = n
        self.res = float('+inf')
        self.dic = collections.defaultdict(list)
        self.no_repeat_set = set()

    def is_prime(self, x):
        if x <= 1:
            return False
        for i in range(2, x):
            if x % i == 0:
                return False
        return True
    
    def dfs(self, idx, s):
        if idx == self.n:
            self.res = min(self.res, s)
            return
        for prime_factor in self.dic[self.alist[idx]]:
            if prime_factor not in self.no_repeat_set:
                self.no_repeat_set.add(prime_factor)
                self.dfs(idx+1, s+prime_factor)
                self.no_repeat_set.remove(prime_factor)
    
    def func(self):
        if self.n <= 0:
            return -1
        for ele in self.alist:
            if ele == 1:
                return -1
            for i in range(2, ele+1):
                if self.is_prime(i) and ele % i == 0:
                    self.dic[ele].append(i)
            if self.dic[ele] == []:
                return -1
        self.dfs(0, 0)
        return -1 if self.res == float('+inf') else self.res


n = int(input().strip())
alist = list(map(int, input().strip().split()))
solution = Solution(alist, n)
print(solution.func())