Starting from the top of a pyramid of numbers like this, you can walk down going one step on the right or on the left, until you reach the bottom row:

                          55
                        94 48
                       95 30 96
                     77 71 26 67

One of such walks is 55 - 94 - 30 - 26.
You can compute the total of the numbers you have seen in such walk,
in this case it's 205.

Your problem is to find the maximum total among all possible paths from the top to the bottom row of the triangle. In the little example above it's 321.



Task

Find the maximum total in the triangle below:

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

Such numbers can be included in the solution code, or read from a "triangle.txt" file.

This task is derived from the Euler Problem #18.




' version 21-06-2015
' compile with: fbc -s console
 
Data "                  55"
Data "                 94 48"
Data "                95 30 96"
Data "               77 71 26 67"
Data "              97 13 76 38 45"
Data "             07 36 79 16 37 68"
Data "            48 07 09 18 70 26 06"
Data "           18 72 79 46 59 79 29 90"
Data "          20 76 87 11 32 07 07 49 18"
Data "         27 83 58 35 71 11 25 57 29 85"
Data "        14 64 36 96 27 11 58 56 92 18 55"
Data "       02 90 03 60 48 49 41 46 33 36 47 23"
Data "      92 50 48 02 36 59 42 79 72 20 82 77 42"
Data "     56 78 38 80 39 75 02 71 66 66 01 03 55 72"
Data "    44 25 67 84 71 67 11 61 40 57 58 89 40 56 36"
Data "   85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52"
Data "  06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15"
Data " 27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93"
Data "END"   ' no more data
 
' ------=< MAIN >=------
 
Dim As String ln
Dim As Integer matrix(1 To 20, 1 To 20)
Dim As Integer x = 1, y, s1, s2, size
 
Do
    Read ln
    ln = Trim(ln)
    If ln = "END" Then Exit Do
    For y = 1 To x
        matrix(x, y) = Val(Left(ln, 2))
        ln = Mid(ln, 4)
    Next
    x += 1
    size += 1
Loop
 
For x = size - 1 To 1 Step - 1
    For y = 1 To x
        s1 = matrix(x + 1, y)
        s2 = matrix(x + 1, y + 1)
        If s1 > s2 Then
            matrix(x, y) += s1
        Else
            matrix(x, y) += s2
        End If
    Next
Next
 
Print 
Print "  maximum triangle path sum ="; matrix(1, 1)
 
' empty keyboard buffer 
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End