""" prob_0060.py """

# usage: python3 prob_0060.py

from itertools import combinations


def primes_less_than(num):
    """ primes less than num """
    nums = list(range(num + 1))
    if num > 0:
        nums[1] = 0
    for i in range(2, num // 2):
        j = num // i
        for k in range(2, j + 1):
            nums[i * k] = 0

    return [n for n in nums if n != 0 and n < num]


print('Generating primes ... ', flush=True, end='')
prime_numbers = {str(i) for i in primes_less_than(100000000)}
print('done.')


def verify_pair(p1, p2):
    """ p1p2 and p2p1 are both prime """
    if f'{p1}{p2}' not in prime_numbers:
        return False
    if f'{p2}{p1}' not in prime_numbers:
        return False

    return True


def check(prime_combo):
    """ check pairs of primes in combo """
    for p1, p2 in combinations(prime_combo, 2):
        if not verify_pair(p1, p2):
            return False

    return True


def solve():
    """ let's go! """
    size = 5

    store = {}
    choices = [(p1, p2) for p1, p2 in combinations(primes_less_than(10000), 2)
               if verify_pair(p1, p2)]

    for p1, p2 in choices:
        key = min(p1, p2)
        values = store.get(key, set())
        values.add(max(p1, p2))
        store[key] = values

    prime_sets = [values | {key} for key, values in store.items()
                  if len(values) >= size - 1]

    output = []
    for prime_set in prime_sets:
        for combo in combinations(prime_set, size):
            if check(combo):
                output.append(sum(combo))
                print(sum(combo), '<-', combo)  # debug

    return min(output)


if __name__ == '__main__':
    print(solve())