Total Triangles

Find the best scoring path through the triangle.

Run 3

Input

94
73 96
28 17 68
66 04 77 24
22 13 70 22 90
92 91 59 76 06 42
28 66 26 31 54 35 08
54 06 69 42 79 86 17 22
32 70 30 61 39 04 10 16 97
57 41 84 44 78 05 61 54 14 36

Expected Output

731