

'''simple docstring'''
from typing import Any


def 	_lowerCAmelCase (						_UpperCamelCase						:					list							,			_UpperCamelCase						:					list							,			_UpperCamelCase						:					dict							,			_UpperCamelCase						:					dict							,			_UpperCamelCase						:					dict							,			)				->      list:
     """simple docstring"""




     _validation(
         _UpperCamelCase							,			_UpperCamelCase							,			_UpperCamelCase							,			_UpperCamelCase							,			_UpperCamelCase							,			)
     # Creates data structures and fill initial step
     _SCREAMING_SNAKE_CASE							   ={}
     _SCREAMING_SNAKE_CASE							   ={}
     for state in states_space:
          _SCREAMING_SNAKE_CASE							   =observations_space[0]
          _SCREAMING_SNAKE_CASE							   =(
              initial_probabilities[state] * emission_probabilities[state][observation]
          )
          _SCREAMING_SNAKE_CASE							   =None

     # Fills the data structure with the probabilities of
     # different transitions and pointers to previous states
     for o in range(1							,			len(_UpperCamelCase    )    ):
          _SCREAMING_SNAKE_CASE							   =observations_space[o]
          _SCREAMING_SNAKE_CASE							   =observations_space[o - 1]
          for state in states_space:
               # Calculates the argmax for probability function
               _SCREAMING_SNAKE_CASE							   =''
               _SCREAMING_SNAKE_CASE							   =-1
               for k_state in states_space:
                    _SCREAMING_SNAKE_CASE							   =(
                        probabilities[(k_state, prior_observation)]
                        * transition_probabilities[k_state][state]
                        * emission_probabilities[state][observation]
                    )
                    if probability > max_probability:
                         _SCREAMING_SNAKE_CASE							   =probability
                         _SCREAMING_SNAKE_CASE							   =k_state

            # Update probabilities and pointers dicts
               _SCREAMING_SNAKE_CASE							   =(
                   probabilities[(arg_max, prior_observation)]
                   * transition_probabilities[arg_max][state]
                   * emission_probabilities[state][observation]
               )

               _SCREAMING_SNAKE_CASE							   =arg_max

    # The final observation
     _SCREAMING_SNAKE_CASE							   =observations_space[len(_UpperCamelCase    ) - 1]

     # argmax for given final observation
     _SCREAMING_SNAKE_CASE							   =''
     _SCREAMING_SNAKE_CASE							   =-1
     for k_state in states_space:
          _SCREAMING_SNAKE_CASE							   =probabilities[(k_state, final_observation)]
          if probability > max_probability:
               _SCREAMING_SNAKE_CASE							   =probability
               _SCREAMING_SNAKE_CASE							   =k_state
     _SCREAMING_SNAKE_CASE							   =arg_max

     # Process pointers backwards
     _SCREAMING_SNAKE_CASE							   =last_state
     _SCREAMING_SNAKE_CASE							   =[]
     for o in range(len(_UpperCamelCase    ) - 1							,			-1							,			-1    ):
          result.append(_UpperCamelCase    )
          _SCREAMING_SNAKE_CASE							   =pointers[previous, observations_space[o]]
     result.reverse()

     return result


def 	_lowerCAmelCase (						_UpperCamelCase						:					Any							,			_UpperCamelCase						:					Any							,			_UpperCamelCase						:					Any							,			_UpperCamelCase						:					Any							,			_UpperCamelCase						:					Any							,			)				->      None:
     """simple docstring"""




     _validate_not_empty(
         _UpperCamelCase							,			_UpperCamelCase							,			_UpperCamelCase							,			_UpperCamelCase							,			_UpperCamelCase							,			)
     _validate_lists(_UpperCamelCase							,			_UpperCamelCase    )
     _validate_dicts(
         _UpperCamelCase							,			_UpperCamelCase							,			_UpperCamelCase    )


def 	_lowerCAmelCase (						_UpperCamelCase						:					Any							,			_UpperCamelCase						:					Any							,			_UpperCamelCase						:					Any							,			_UpperCamelCase						:					Any							,			_UpperCamelCase						:					Any							,			)				->      None:
     """simple docstring"""




     if not all(
         [
             observations_space,
             states_space,
             initial_probabilities,
             transition_probabilities,
             emission_probabilities,
         ]    ):
          raise ValueError('There\'s an empty parameter'    )


def 	_lowerCAmelCase (						_UpperCamelCase						:					Any							,			_UpperCamelCase						:					Any    )				->      None:
     """simple docstring"""




     _validate_list(_UpperCamelCase							,			'observations_space'    )
     _validate_list(_UpperCamelCase							,			'states_space'    )


def 	_lowerCAmelCase (						_UpperCamelCase						:					Any							,			_UpperCamelCase						:					str    )				->      None:
     """simple docstring"""




     if not isinstance(_object							,			_UpperCamelCase    ):
          _SCREAMING_SNAKE_CASE							   =f"{var_name} must be a list"
          raise ValueError(_UpperCamelCase    )
     else:
          for x in _object:
               if not isinstance(_UpperCamelCase							,			_UpperCamelCase    ):
                    _SCREAMING_SNAKE_CASE							   =f"{var_name} must be a list of strings"
                    raise ValueError(_UpperCamelCase    )


def 	_lowerCAmelCase (						_UpperCamelCase						:					Any							,			_UpperCamelCase						:					Any							,			_UpperCamelCase						:					Any							,			)				->      None:
     """simple docstring"""




     _validate_dict(_UpperCamelCase							,			'initial_probabilities'							,			_UpperCamelCase    )
     _validate_nested_dict(_UpperCamelCase							,			'transition_probabilities'    )
     _validate_nested_dict(_UpperCamelCase							,			'emission_probabilities'    )


def 	_lowerCAmelCase (						_UpperCamelCase						:					Any							,			_UpperCamelCase						:					str    )				->      None:
     """simple docstring"""




     _validate_dict(_object							,			_UpperCamelCase							,			_UpperCamelCase    )
     for x in _object.values():
          _validate_dict(_UpperCamelCase							,			_UpperCamelCase							,			_UpperCamelCase							,			_UpperCamelCase    )


def 	_lowerCAmelCase (						_UpperCamelCase						:					Any							,			_UpperCamelCase						:					str							,			_UpperCamelCase						:					type							,			_UpperCamelCase						:					bool = False    )				->      None:
     """simple docstring"""




     if not isinstance(_object							,			_UpperCamelCase    ):
          _SCREAMING_SNAKE_CASE							   =f"{var_name} must be a dict"
          raise ValueError(_UpperCamelCase    )
     if not all(isinstance(_UpperCamelCase							,			_UpperCamelCase    ) for x in _object    ):
          _SCREAMING_SNAKE_CASE							   =f"{var_name} all keys must be strings"
          raise ValueError(_UpperCamelCase    )
     if not all(isinstance(_UpperCamelCase							,			_UpperCamelCase    ) for x in _object.values()    ):
          _SCREAMING_SNAKE_CASE							   ='nested dictionary ' if nested else ''
          _SCREAMING_SNAKE_CASE							   =f"{var_name} {nested_text}all values must be {value_type.__name__}"
          raise ValueError(_UpperCamelCase    )


if __name__ == "__main__":
     from doctest import testmod

     testmod()



'''simple docstring'''
import os


def 	_lowerCAmelCase (						)				->      List[str]:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							   =os.path.dirname(os.path.realpath(_UpperCamelCase    )    )
     _SCREAMING_SNAKE_CASE							   =os.path.join(_UpperCamelCase							,			'triangle.txt'    )

     with open(_UpperCamelCase    ) as f:
          _SCREAMING_SNAKE_CASE							   =f.readlines()

     _SCREAMING_SNAKE_CASE							   =[]
     for line in triangle:
          _SCREAMING_SNAKE_CASE							   =[]
          for number in line.strip().split(' '    ):
               numbers_from_line.append(int(_UpperCamelCase    )    )
          a.append(_UpperCamelCase    )

     for i in range(1							,			len(_UpperCamelCase    )    ):
          for j in range(len(a[i]    )    ):
               _SCREAMING_SNAKE_CASE							   =a[i - 1][j] if j != len(a[i - 1]    ) else 0
               _SCREAMING_SNAKE_CASE							   =a[i - 1][j - 1] if j > 0 else 0
               a[i][j] += max(_UpperCamelCase							,			_UpperCamelCase    )
     return max(a[-1]    )


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