Total Triangles

Find the best scoring path through the triangle.

Run 5

Input

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

Expected Output

3562