import copy

input = []

# Reads the input from a file, assuming that the input is stored in a file named "input.txt"
def read_file(filename):
    with open(filename, "r") as file:
        for line in file:
            array = line.strip().split(" ")
            new_array = []
            for i in array:
                new_array.append(int(i))
            input.append(new_array)


read_file("input.txt")


# Checks if the number is a prime number
def isPrime(n):
    if n == 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False

    return True


max_sum = 0
max_step = 0
max_numbers = []


def find_total(index=0, step=0, visited_numbers=[]):
    global max_sum
    global max_step
    global max_numbers

    new_array = copy.copy(visited_numbers)
    new_array.append(input[step][index])

    print(new_array)

    # If the program reached the and of the tree
    if step == len(input)-1:
        if step == max_step:
            if sum(new_array) > max_sum:
                max_sum = sum(new_array)
                max_numbers = new_array

        elif step > max_step:
            max_step = step
            max_sum = sum(new_array)
            max_numbers = new_array

    # If current node has no more children that is not prime
    elif isPrime(input[step+1][index]) and isPrime(input[step+1][index+1]):
        if step == max_step:
            if sum(new_array) > max_sum:
                max_sum = sum(new_array)
                max_numbers = new_array

        elif step > max_step:
            max_step = step
            max_sum = sum(new_array)
            max_numbers = new_array

    # If the current node has more children that are not prime, then repeat the process for the next children
    else:
        if not isPrime(input[step+1][index]):
            find_total(index, step+1, new_array)
        if not isPrime(input[step+1][index+1]):
            find_total(index+1, step+1, new_array)


# Run the algorithm which will assign the max sum to the max_sum variable
find_total()
print("Max Sum = " + str(max_sum))
print("The Sequence of numbers for the max sum : ", end="")
print(max_numbers)