def is_prime(num):
    temp = True
    if num > 1:
        for i in range(2, num):
            if (num % i) == 0:
                temp = False
                break;
    return temp

def maxPathSum(tri, m, n):
    if (is_prime(tri[0][0])):
        sum = tri[0][0]
    else:
        sum = 0

    for i in range(m - 1, -1, -1):
        for j in range(i + 1):
            if(not is_prime(tri[i+1][j]) and not is_prime(tri[i+1][j+1])):
                if(tri[i+1][j] > tri[i+1][j+1]):
                    tri[i][j] += tri[i+1][j]
                else:
                    tri[i][j] += tri[i+1][j+1]
            elif(not is_prime(tri[i+1][j])):
                tri[i][j] += tri[i + 1][j]
            else:
                tri[i][j] += tri[i + 1][j + 1]


    return tri[0][0] + sum

def find_a_path(array, height):

    sum = array[0]
    temp = 0

    for i in range(1,height):
        if(not is_prime(array[temp+1*i]) and  not is_prime(array[temp+1*i + 1])):
            if(array[temp+1*i]>=array[temp+1*i+ 1]):
                sum += array[temp+1*i]
                temp = temp + 1 * i
        elif(not is_prime(array[temp+1*i]) and  is_prime(array[temp+1*i + 1])):
            sum += array[temp + 1 * i]
            temp = temp + 1 * i
        elif( is_prime(array[temp+1*i]) and  not is_prime(array[temp+1*i + 1])):
            sum += array[temp + 1 * i + 1]
            temp = temp + 1 * i + 1
        else:
            sum += array[temp + 1 * i + 1]
            temp = temp + 1 * i + 1
    return sum

if __name__ == '__main__':
    tri = [[1, 0, 0, 0],
           [8, 4, 0, 0],
           [2, 6, 9, 0],
           [8, 5, 9, 3] ]

    tri2 = [[215,0,0,0,0,0,0,0,0,0,0,0,0,0],
            [193,124,0,0,0,0,0,0,0,0,0,0,0,0,0],
            [117,237,235,0,0,0,0,0,0,0,0,0,0,0,0],
            [218,935,347,235,0,0,0,0,0,0,0,0,0,0,0],
            [320,804,522,417,345,0,0,0,0,0,0,0,0,0,0],
            [229,601,723,835,133,124,0,0,0,0,0,0,0,0,0],
            [248,202,277,433,207,263,257,0,0,0,0,0,0,0,0],
            [359,464,504,528,516,716,871,182,0,0,0,0,0,0,0],
            [461,441,426,656,863,560,380,171,923,0,0,0,0,0,0],
            [381,348,573,533,447,632,387,176,975,449,0,0,0,0,0],
            [223 ,711, 445 ,645 ,245 ,543, 931, 532, 937, 541, 444,0,0,0,0],
            [330 ,131, 333 ,928 ,377 ,733 ,17 ,778 ,839 ,168 ,197 ,197, 0, 0, 0],
            [131 ,171, 522 ,137 ,217, 224 ,291 ,413 ,528 ,520 ,227 ,229 ,928, 0, 0],
            [223, 626 ,34 ,683, 839, 53 ,627 ,310 ,713 ,999 ,629, 817 ,410 ,121, 0],
            [924 ,622, 911 ,233 ,325, 139, 721, 218, 253, 223, 107, 233, 230, 124, 233]]

    print(maxPathSum(tri, 3, 3))
    print(maxPathSum(tri2, 14, 14))