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.




 
PROGRAM TRIANGLE_PATH
 
CONST ROW=18
 
DIM TRI[200]
 
!
! for rosettacode,org
!
 
FUNCTION MAX(X,Y)
   MAX=-X*(X>=Y)-Y*(X<Y)
END FUNCTION
 
BEGIN
 
     DATA(55)
     DATA(94,48)
     DATA(95,30,96)
     DATA(77,71,26,67)
     DATA(97,13,76,38,45)
     DATA(7,36,79,16,37,68)
     DATA(48,7,9,18,70,26,6)
     DATA(18,72,79,46,59,79,29,90)
     DATA(20,76,87,11,32,7,7,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(2,90,3,60,48,49,41,46,33,36,47,23)
     DATA(92,50,48,2,36,59,42,79,72,20,82,77,42)
     DATA(56,78,38,80,39,75,2,71,66,66,1,3,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,1,1,99,89,52)
     DATA(6,71,28,75,94,48,37,10,23,51,6,48,53,18,74,98,15)
     DATA(27,2,92,23,8,71,76,84,15,52,92,63,81,10,44,10,69,93)
 
     PRINT(CHR$(12);) !CLS
     LUNG=ROW*(ROW+1)/2
     FOR I%=0 TO LUNG-1 DO
        READ(TRI[I%])
     END FOR
 
     BSE=(SQR(8*LUNG+1)-1)/2
     STP=BSE-1
     STEPC=0
 
     FOR I%=LUNG-BSE-1 TO 0 STEP -1 DO
        TRI[I%]=TRI[I%]+MAX(TRI[I%+STP],TRI[I%+STP+1])
        STEPC=STEPC+1
        IF STEPC=STP THEN
             STP=STP-1
             STEPC=0
        END IF
     END FOR
 
     PRINT(TRI[0])
END PROGRAM
 