class Max(object):
    def __init__(self, l):
        "parse triangle, initialize cache"
        self.l = l
        self.t = [
            map(int,filter(lambda x:len(x)>0, x.split(" ")))
            for x in l
        ]
        self.cache = {}

    def maxsub(self, r=0, c=0):
        "compute max path starting at (r,c)"
        saved = self.cache.get((r,c))
        if saved:
            return saved

        if r >= len(self.t):
            answer = (0, [], [])
        else:
            v = self.t[r][c]
            s1, l1, c1 = self.maxsub(r+1, c)
            s2, l2, c2 = self.maxsub(r+1, c+1)
            if s1 > s2:
                answer = (v+s1, [v]+l1, [c]+c1)
            else:
                answer = (v+s2, [v]+l2, [c]+c2)
        self.cache[(r,c)] = answer
        return answer

    def report(self, r=0, c=0):
        "find and report max path"
        m = self.maxsub(r, c)
        print
        print "\n".join(self.l)
        print "maxsum:%s\nvalues:%s\ncolumns:%s" % m

def main():
    with file('p067_triangle.txt') as f:
        L = f.readlines()
    Max(L).report()

if __name__ == '__main__':
    main()