






"""simple docstring"""
from __future__ import annotations

A_			: Optional[Any]				=			[2, 1, 4, 5, 6, 0, 8, 9, 1, 2, 0, 6, 4, 2, 0, 6, 5, 3, 2, 7]



class 		a_      :







      '''simple docstring'''

      def __init__(self,     lowerCamelCase_					):

       '''simple docstring'''



       lowerCamelCase__     :			int     				=						-1
       lowerCamelCase__     :			int     				=						-1
       lowerCamelCase__     :			list[int]     				=						[-1] * length
       lowerCamelCase__     :			Node | None     				=						None
       lowerCamelCase__     :			Node | None     				=						None





      def __repr__(self					):

       '''simple docstring'''



       return f'''Node(min_value={self.minn} max_value={self.maxx})'''






def        lowerCamelCase_  (						_lowerCamelCase				):
 lowerCamelCase__     :			List[str]     				=						Node(len(_lowerCamelCase				)				)
 lowerCamelCase__				,     lowerCamelCase__     :			Union[str, Any]     				=						min(_lowerCamelCase				), max(_lowerCamelCase				)
 # Leaf node case where the node contains only one unique value
 if root.minn == root.maxx:
  return root
 lowerCamelCase__     :			Optional[Any]     				=						(root.minn + root.maxx) // 2

 lowerCamelCase__     :			list[int]     				=						[]
 lowerCamelCase__     :			list[int]     				=						[]

 for index, num in enumerate(_lowerCamelCase				):
  if num <= pivot:
   left_arr.append(_lowerCamelCase				)
  else:
   right_arr.append(_lowerCamelCase				)
  lowerCamelCase__     :			Dict     				=						len(_lowerCamelCase				)
 lowerCamelCase__     :			Union[str, Any]     				=						build_tree(_lowerCamelCase				)
 lowerCamelCase__     :			int     				=						build_tree(_lowerCamelCase				)
 return root






def        lowerCamelCase_  (						_lowerCamelCase			,   _lowerCamelCase			,   _lowerCamelCase				):
 if index < 0 or node is None:
  return 0
 # Leaf node cases
 if node.minn == node.maxx:
  return index + 1 if node.minn == num else 0
 lowerCamelCase__     :			int     				=						(node.minn + node.maxx) // 2
 if num <= pivot:
  # go the left subtree and map index to the left subtree
  return rank_till_index(node.left			,   _lowerCamelCase			,   node.map_left[index] - 1				)
 else:
  # go to the right subtree and map index to the right subtree
  return rank_till_index(node.right			,   _lowerCamelCase			,   index - node.map_left[index]				)






def        lowerCamelCase_  (						_lowerCamelCase			,   _lowerCamelCase			,   _lowerCamelCase			,   _lowerCamelCase				):
 if start > end:
  return 0
 lowerCamelCase__     :			Optional[Any]     				=						rank_till_index(_lowerCamelCase			,   _lowerCamelCase			,   _lowerCamelCase				)
 lowerCamelCase__     :			int     				=						rank_till_index(_lowerCamelCase			,   _lowerCamelCase			,   start - 1				)
 return rank_till_end - rank_before_start






def        lowerCamelCase_  (						_lowerCamelCase			,   _lowerCamelCase			,   _lowerCamelCase			,   _lowerCamelCase				):
 if index > (end - start) or start > end or node is None:
  return -1
 # Leaf node case
 if node.minn == node.maxx:
  return node.minn
 # Number of elements in the left subtree in interval [start, end]
 lowerCamelCase__     :			Optional[Any]     				=						node.map_left[end] - (
     node.map_left[start - 1] if start else 0
 )
 if num_elements_in_left_tree > index:
  return quantile(
      node.left			,   _lowerCamelCase			,   (node.map_left[start - 1] if start else 0)			,   node.map_left[end] - 1			,   )
 else:
  return quantile(
      node.right			,   index - num_elements_in_left_tree			,   start - (node.map_left[start - 1] if start else 0)			,   end - node.map_left[end]			,   )






def        lowerCamelCase_  (						_lowerCamelCase			,   _lowerCamelCase			,   _lowerCamelCase			,   _lowerCamelCase			,   _lowerCamelCase				):
 if (
     start > end
     or node is None
     or start_num > end_num
     or node.minn > end_num
     or node.maxx < start_num
 ):
  return 0
 if start_num <= node.minn and node.maxx <= end_num:
  return end - start + 1
 lowerCamelCase__     :			List[Any]     				=						range_counting(
     node.left			,   (node.map_left[start - 1] if start else 0)			,   node.map_left[end] - 1			,   _lowerCamelCase			,   _lowerCamelCase			,   )
 lowerCamelCase__     :			str     				=						range_counting(
     node.right			,   start - (node.map_left[start - 1] if start else 0)			,   end - node.map_left[end]			,   _lowerCamelCase			,   _lowerCamelCase			,   )
 return left + right


if __name__ == "__main__":
      import doctest

      doctest.testmod()









"""simple docstring"""
import os






def        lowerCamelCase_  (						):
 lowerCamelCase__     :			List[Any]     				=						os.path.dirname(os.path.realpath(_lowerCamelCase				)				)
 lowerCamelCase__     :			Any     				=						os.path.join(_lowerCamelCase			,   'triangle.txt'				)

 with open(_lowerCamelCase				) as in_file:
  lowerCamelCase__     :			Dict     				=						[[int(_lowerCamelCase				) for i in line.split()] for line in in_file]

 while len(_lowerCamelCase				) != 1:
  lowerCamelCase__     :			Dict     				=						triangle.pop()
  lowerCamelCase__     :			Optional[Any]     				=						triangle[-1]
  for j in range(len(_lowerCamelCase				) - 1				):
   curr_row[j] += max(last_row[j]			,   last_row[j + 1]				)
 return triangle[0][0]


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

