def not_prime(num):

    if num > 1:
       # check for factors
       for i in range(2,num):
           if (num % i) == 0:
               return True
               print(i,"times",num//i,"is",num)
               break
       else:
           return False
           
    # if input number is less than
    # or equal to 1, it is not prime
    else:
       return True





def maxPathSum(tree, m, n): 
  
    # loop for bottom-up calculation 
    for i in range(m-1, -1, -1): 
        for j in range(i+1): 
  
            
            if (tri[i+1][j] > tri[i+1][j+1] and not_prime(tri[i+1][j])): 
                tri[i][j] += tri[i+1][j] 
            elif not_prime(tri[i+1][j+1]): 
                tri[i][j] += tri[i+1][j+1] 
  
    
    return tri[0][0] 
 

tri = [[1,0,0,0],
       [8,4,0,0],
       [2,6,9,0],
       [8,5,9,3]]
print maxPathSum(tree, 3, 3)