


import os
def 	_lowerCamelCase  (		)			->			List[Any]:

   '''simple docstring'''






   UpperCamelCase__ :			List[Any] 						=os.path.dirname(os.path.realpath(A_      )      )
   UpperCamelCase__ :			str 						=os.path.join(A_							,  "triangle.txt"      )

   with open(A_      ) as f:
      UpperCamelCase__ :			List[str] 						=f.readlines()

   UpperCamelCase__ :			Dict 						=[[int(A_      ) for y in x.rstrip("\r\n"      ).split(" "      )] for x in triangle]

   for i in range(1							,  len(A_      )      ):
      for j in range(len(a[i]      )      ):
         UpperCamelCase__ :			Union[str, Any] 						=a[i - 1][j] if j != len(a[i - 1]      ) else 0
         UpperCamelCase__ :			List[Any] 						=a[i - 1][j - 1] if j > 0 else 0
         a[i][j] += max(A_							,  A_      )
   return max(a[-1]      )


if __name__ == "__main__":
     print(solution())



from __future__ import annotations
def lowerCamelCase_       (			A			:      list[int]						):




      """simple docstring"""
      if not list_of_ints:
            return []

      if min(A						) < 0:
            raise ValueError('''All numbers must be positive'''						)

      lowerCAmelCase_						=      max(len(bin(A						)[2:]						) for x in list_of_ints						)
      return _msd_radix_sort(A		,					A						)
def lowerCamelCase_       (			A			:      list[int]		,					A			:      int						):




      """simple docstring"""
      if bit_position == 0 or len(A						) in [0, 1]:
            return list_of_ints

      lowerCAmelCase_						=      []
      lowerCAmelCase_						=      []
      # Split numbers based on bit at bit_position from the right
      for number in list_of_ints:
            if (number >> (bit_position - 1)) & 1:
                  # number has a one at bit bit_position
                  ones.append(A						)
            else:
                  # number has a zero at bit bit_position
                  zeros.append(A						)

    # recursively split both lists further
      lowerCAmelCase_						=      _msd_radix_sort(A		,					bit_position - 1						)
      lowerCAmelCase_						=      _msd_radix_sort(A		,					bit_position - 1						)

      # recombine lists
      lowerCAmelCase_						=      zeros
      res.extend(A						)

      return res
def lowerCamelCase_       (			A			:      list[int]						):




      """simple docstring"""
      lowerCAmelCase_						=      len(A						)
      if not list_of_ints or length == 1:
            return

      if min(A						) < 0:
            raise ValueError('''All numbers must be positive'''						)

      lowerCAmelCase_						=      max(len(bin(A						)[2:]						) for x in list_of_ints						)
      _msd_radix_sort_inplace(A		,					A		,					0		,					A						)
def lowerCamelCase_       (			A			:      list[int]		,					A			:      int		,					A			:      int		,					A			:      int						):




      """simple docstring"""
      if bit_position == 0 or end_index - begin_index <= 1:
            return

      bit_position -= 1

      lowerCAmelCase_						=      begin_index
      lowerCAmelCase_						=      end_index - 1
      while i <= j:
            lowerCAmelCase_						=      False
            if not (list_of_ints[i] >> bit_position) & 1:
                  # found zero at the beginning
                  i += 1
                  lowerCAmelCase_						=      True
            if (list_of_ints[j] >> bit_position) & 1:
                  # found one at the end
                  j -= 1
                  lowerCAmelCase_						=      True

            if changed:
                  continue

            lowerCAmelCase_			,		lowerCAmelCase_						=      list_of_ints[j], list_of_ints[i]
            j -= 1
            if j != i:
                  i += 1

      _msd_radix_sort_inplace(A		,					A		,					A		,					A						)
      _msd_radix_sort_inplace(A		,					A		,					A		,					A						)


if __name__ == "__main__":
 import doctest

 doctest.testmod()



