Total Triangles

Find the best scoring path through the triangle.

Run 4

Input

46
27 66
98 07 57
45 54 12 19
94 70 59 66 29
47 70 29 49 68 71
62 13 72 26 35 46 06
31 76 70 15 52 73 30 51
07 40 48 61 23 65 30 75 20
36 66 46 03 65 52 00 62 81 14

Expected Output

648