Total Triangles

Find the best scoring path through the triangle.

Run 6

Input

13
58 12
47 21 40
11 78 80 30
85 08 31 18 47
53 35 75 18 37 18
29 62 45 00 03 85 52
97 97 60 99 83 41 65 13
41 52 70 78 33 75 80 72 57
71 29 80 55 92 26 77 14 81 35
86 45 48 07 58 34 20 32 74 27 56
15 34 06 62 94 09 64 64 31 91 24 91
25 95 10 02 14 40 75 57 71 80 90 75 42
63 71 58 27 68 50 58 95 78 53 65 16 58 76
67 78 73 39 92 51 49 60 81 58 27 74 37 10 85
23 80 98 48 84 38 42 35 25 14 24 14 19 27 89 35
00 92 84 29 41 96 35 58 30 13 93 23 43 75 27 21 32
30 65 13 48 19 51 02 10 65 39 56 30 02 16 38 62 16 06
83 64 85 49 94 79 17 47 20 46 48 48 98 53 87 11 85 28 37
47 22 02 34 50 82 66 40 78 24 51 03 91 70 93 29 00 53 78 31
27 10 45 86 52 14 74 36 45 88 09 91 10 26 43 71 86 21 34 84 73
59 83 72 84 70 84 22 63 76 08 35 04 24 06 75 97 40 14 93 62 13 75
46 54 25 24 60 48 42 59 33 04 74 65 76 26 74 74 15 72 24 06 59 21 21
25 88 67 49 41 47 60 86 26 68 66 75 59 72 15 87 62 22 62 92 96 96 16 22
03 23 08 18 61 87 39 36 24 08 47 11 99 32 76 88 59 91 40 29 08 41 94 68 36
96 40 24 77 03 01 01 21 27 54 00 10 32 20 84 95 85 48 57 90 09 68 13 52 68 38
40 84 37 94 16 85 92 41 21 89 33 73 60 96 74 85 49 55 35 70 96 24 51 26 71 91 67
81 37 37 61 91 81 01 22 53 57 08 24 99 04 52 62 22 45 84 67 56 13 45 24 83 62 06 40
36 66 39 23 07 60 64 97 58 68 26 12 38 24 32 21 63 57 28 28 19 24 03 69 97 86 27 82 60
17 17 38 30 50 16 67 43 65 25 51 51 70 30 90 81 08 29 90 69 15 91 84 63 37 69 68 45 51 64
54 12 26 49 11 65 02 83 34 02 20 68 93 71 55 76 37 00 80 39 30 38 09 74 60 73 76 86 99 32 67
41 80 31 06 10 19 07 48 85 15 30 46 66 57 05 67 88 03 54 57 67 08 66 31 35 17 43 14 51 42 68 87
68 27 04 42 15 76 97 53 02 13 00 87 66 27 43 25 71 79 04 41 13 70 12 90 43 30 96 68 31 24 07 36 95
93 74 81 41 89 72 78 36 05 65 19 65 24 09 96 37 65 72 87 36 04 50 56 05 25 02 03 94 18 34 70 94 32 69
27 12 81 05 62 25 87 44 05 72 84 61 18 48 36 67 61 42 91 42 74 43 31 97 19 39 68 50 10 83 82 78 71 31 82
08 80 63 63 62 97 70 20 92 04 78 44 60 62 60 54 05 87 53 55 55 07 84 32 23 40 84 28 87 44 82 49 44 55 04 32
19 79 55 37 16 87 79 51 40 57 39 16 24 47 75 06 76 97 45 72 28 68 75 83 76 59 08 63 05 17 23 61 04 23 08 02 93
48 57 46 76 89 34 55 89 36 70 25 04 74 62 46 99 26 34 87 81 28 37 16 50 87 66 89 38 95 53 85 13 37 12 48 21 46 25
89 87 96 60 27 78 91 80 04 35 19 44 78 16 42 31 59 44 29 59 41 40 00 37 77 34 89 54 82 39 90 40 58 53 14 34 42 43 11
89 15 04 58 50 25 24 59 44 75 08 49 95 12 76 15 83 51 50 83 17 53 40 02 79 34 04 89 20 99 03 54 96 33 28 53 54 42 65 52
38 89 42 74 08 32 65 17 09 97 77 68 72 29 55 45 39 78 21 92 99 71 95 29 79 13 28 45 89 51 08 51 05 22 47 97 25 61 02 31 40
40 17 98 41 00 22 39 44 85 79 53 94 57 84 30 12 55 51 11 53 93 16 90 07 49 85 49 44 58 16 16 19 18 98 96 70 83 30 82 76 25 64
88 03 86 79 63 04 76 45 71 91 82 99 53 53 84 58 85 29 03 71 13 46 17 67 19 11 38 74 73 49 36 32 20 63 36 11 41 53 01 95 68 29 63
93 65 28 82 37 97 70 13 53 86 57 40 48 62 50 45 07 25 01 13 77 76 77 87 50 92 87 54 12 25 55 52 18 76 24 23 15 62 37 88 57 49 54 68
64 88 42 21 45 85 03 70 22 52 44 10 84 64 17 03 27 88 95 11 06 90 94 31 71 44 26 22 36 69 40 30 59 53 77 19 60 77 75 48 59 92 15 31 47
80 93 45 38 67 17 33 07 30 93 08 69 54 91 96 04 80 57 27 80 21 21 25 50 15 47 15 56 13 46 79 17 54 34 06 11 90 35 08 04 46 27 47 30 20 45
49 85 78 86 13 35 36 72 58 04 58 86 96 35 43 51 82 80 73 49 62 00 47 82 33 09 56 03 16 72 44 65 96 61 98 04 15 15 66 84 57 77 40 11 59 24 74
98 82 93 82 00 71 48 31 60 45 28 33 43 96 62 67 97 19 32 60 43 45 63 72 03 27 21 42 79 18 03 55 69 70 05 33 40 23 83 09 27 32 19 91 45 82 58 71
08 12 76 44 05 45 92 37 15 06 67 64 63 70 29 58 37 66 96 32 69 91 79 98 52 14 89 98 31 24 49 80 04 04 57 75 87 63 78 63 13 63 10 46 40 38 80 95 45
37 38 58 94 78 71 12 41 55 69 98 99 36 52 44 78 65 37 10 66 34 86 15 59 93 93 96 60 17 42 85 85 12 97 75 41 87 59 36 49 14 84 80 29 45 03 21 51 27 10

Expected Output

3581