Total Triangles

Find the best scoring path through the triangle.

Run 6

Input

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

Expected Output

3588