global highest_sum;
global g_path;

def is_even(num):
    return num % 2 == 0;

matrix=[[215,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
        [192,124,0,0,0,0,0,0,0,0,0,0,0,0,0],
        [117,269,442,0,0,0,0,0,0,0,0,0,0,0,0],
        [218,836,347,235,0,0,0,0,0,0,0,0,0,0,0],
        [320,805,522,417,345,0,0,0,0,0,0,0,0,0,0],
        [229,601,728,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,448,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,376,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,52,627,310,713,999,629,817,410,121,0],
        [924,622,911,233,325,139,721,218,253,223,107,233,230,124,233]]

def find_highest_sum(row_index, column_index, previous_even, current_sum, path, direction):
    global highest_sum;
    global g_path;
    if(row_index >= len(matrix) or column_index >= len(matrix[row_index])):
        return;
    current_value = matrix[row_index][column_index];
    if(direction != ''):
        path += column_index*('  ');
        path += (direction) + '\n';
    path += column_index*('  ');
    path += str(current_value) + '\n';
    if((previous_even and is_even(current_value)) or (not previous_even and not is_even(current_value)) and row_index != 0):
        print('Invalid path');
        print(path);
        return;
    current_sum += current_value;
    if(current_sum > highest_sum):
        highest_sum = current_sum;
        g_path = path;
    find_highest_sum(row_index + 1, column_index, is_even(current_value), current_sum, path,'↓')
    find_highest_sum(row_index + 1, column_index + 1, is_even(current_value), current_sum, path, '↘')


highest_sum = 0;
find_highest_sum(0, 0, False, 0, '', '');

print(highest_sum)
print('Best path')
print(g_path)