#!/usr/bin/python

datain = [l.strip().split(" ") for l in open("triangle.txt").read().split("\n") \
            if len(l) != 0]

#dynamic programming! No idea why it's called that...
#m is lines of lists of [value, running-total, direction-total-from]
#/me longs for enums
VALUE = 0
RUNNING_TOTAL = 1
PREVIOUS = 2
LEFT = 0
RIGHT = 1

m = [[[int(d), 0, None] for d in l] for l in datain]

for l in range(1, len(m)):
    line_above = m[l-1]
    line = m[l]
    #For each item on the line, identify the item above that is bigger
    #First item (nothing above-left)
    line[0][RUNNING_TOTAL] = line_above[0][RUNNING_TOTAL] + line[0][VALUE]
    line[0][PREVIOUS] = line_above[0]

    for n in range(1, len(line)-2):
        #Do it for others in the line
        if line_above[n-1][RUNNING_TOTAL] > line_above[n][RUNNING_TOTAL]:
            #Sum from above-left
            line[n][RUNNING_TOTAL] = line_above[n-1][RUNNING_TOTAL] + line[n][VALUE]
            line[n][PREVIOUS] = line_above[n-1]
        else:
            #Sum from above-right
            line[n][RUNNING_TOTAL] = line_above[n][RUNNING_TOTAL] + line[n][VALUE]
            line[n][PREVIOUS] = line_above[n]

    #Last item (nothing above-right)
    n = len(line)-1
    line[n][RUNNING_TOTAL] = line_above[len(line_above)-1][RUNNING_TOTAL] + line[n][VALUE]
    line[n][PREVIOUS] = line_above[len(line_above)-1]

#Now find the route (backwards)
#Find the end
best = None
best_total = 0
for n in m[len(m)-1]:
    if n[RUNNING_TOTAL] > best_total:
        best = n

print "Total: %d" % n[RUNNING_TOTAL]
winners = [n]
while n[PREVIOUS] != None:
    n = n[PREVIOUS]
    winners.insert(0, n)

print [n[VALUE] for n in winners]