



'''simple docstring'''







from __future__ import annotations







def  SCREAMING_SNAKE_CASE__ (				SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE     ):
		SCREAMING_SNAKE_CASE_						:Tuple										=      0
		SCREAMING_SNAKE_CASE_						:Optional[Any]										=      len(lowerCamelCase__     ) - 1
		while left <= right:
				SCREAMING_SNAKE_CASE_						:List[Any]										=      (left + right) // 2
				if left == right:
						if sorted_list[middle] < item:
								SCREAMING_SNAKE_CASE_						:Tuple										=      middle + 1
						break
				elif sorted_list[middle] < item:
						SCREAMING_SNAKE_CASE_						:Optional[int]										=      middle + 1
				else:
						SCREAMING_SNAKE_CASE_						:Dict										=      middle - 1
		sorted_list.insert(lowerCamelCase__ ,		lowerCamelCase__     )
		return sorted_list







def  SCREAMING_SNAKE_CASE__ (				SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE     ):
		SCREAMING_SNAKE_CASE_						:Tuple										=      []
		while left and right:
				if left[0][0] < right[0][0]:
						result.append(left.pop(0     )     )
				else:
						result.append(right.pop(0     )     )
		return result + left + right







def  SCREAMING_SNAKE_CASE__ (				SCREAMING_SNAKE_CASE     ):
		SCREAMING_SNAKE_CASE_						:Optional[Any]										=      len(lowerCamelCase__     )
		if length <= 1:
				return list_ad
		SCREAMING_SNAKE_CASE_						:Dict										=      length // 2
		return merge(sortlist_ad(list_ad[:middle]     ) ,		sortlist_ad(list_ad[middle:]     )     )







def  SCREAMING_SNAKE_CASE__ (				SCREAMING_SNAKE_CASE     ):

		if len(lowerCamelCase__     ) <= 1:
				return collection
		SCREAMING_SNAKE_CASE_						:int										=      []
		SCREAMING_SNAKE_CASE_						:Optional[int]										=      False
		for i in range(0 ,		len(lowerCamelCase__     ) ,		2     ):
				if i == len(lowerCamelCase__     ) - 1:
						SCREAMING_SNAKE_CASE_						:int										=      True
				else:
						if collection[i] < collection[i + 1]:
								two_paired_list.append([collection[i], collection[i + 1]]     )
						else:
								two_paired_list.append([collection[i + 1], collection[i]]     )
		SCREAMING_SNAKE_CASE_						:Dict										=      sortlist_ad(lowerCamelCase__     )
		SCREAMING_SNAKE_CASE_						:List[Any]										=      [i[0] for i in sorted_list_ad]
		result.append(sorted_list_ad[-1][1]     )
		if has_last_odd_item:
				SCREAMING_SNAKE_CASE_						:str										=      collection[-1]
				SCREAMING_SNAKE_CASE_						:List[str]										=      binary_search_insertion(lowerCamelCase__ ,		lowerCamelCase__     )
		SCREAMING_SNAKE_CASE_						:Union[str, Any]										=      False
		for i in range(len(lowerCamelCase__     ) - 1     ):
				if result[i] == collection[-1] and has_last_odd_item:
						SCREAMING_SNAKE_CASE_						:Optional[Any]										=      True
				SCREAMING_SNAKE_CASE_						:List[Any]										=      sorted_list_ad[i][1]
				# If last_odd_item is inserted before the item's index,
				# you should forward index one more.
				if is_last_odd_item_inserted_before_this_index:
						SCREAMING_SNAKE_CASE_						:List[str]										=      result[: i + 2] + binary_search_insertion(result[i + 2 :] ,		lowerCamelCase__     )
				else:
						SCREAMING_SNAKE_CASE_						:List[str]										=      result[: i + 1] + binary_search_insertion(result[i + 1 :] ,		lowerCamelCase__     )

		return result


if __name__ == "__main__":
							SCREAMING_SNAKE_CASE__     : Optional[int]				=   input("""Enter numbers separated by a comma:\n""").strip()
							SCREAMING_SNAKE_CASE__     : Optional[Any]				=   [int(item) for item in user_input.split(""",""")]
							print(merge_insertion_sort(unsorted))






'''simple docstring'''




import os




def     snake_case__     (			) -> int:
					A_			:  List[str]			=				os.path.dirname(os.path.realpath(lowerCamelCase__      )      )
					A_			:  str			=				os.path.join(lowerCamelCase__      ,		'''triangle.txt'''      )

					with open(lowerCamelCase__      ) as in_file:
										A_			:  List[str]			=				[[int(lowerCamelCase__      ) for i in line.split()] for line in in_file]

					while len(lowerCamelCase__      ) != 1:
										A_			:  List[str]			=				triangle.pop()
										A_			:  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())



