






"""simple docstring"""

def 		__lowerCamelCase	(  __UpperCamelCase      ,       __UpperCamelCase       )						->    bool:

		"""simple docstring"""







		lowerCAmelCase_   :							Optional[Any]									=			len(__UpperCamelCase       ) + 1
		lowerCAmelCase_   :							Tuple									=			len(__UpperCamelCase       ) + 1

		# dp is a 2d matrix where dp[i][j] denotes whether prefix string of
		# length i of input_string matches with prefix string of length j of
		# given pattern.
		# "dp" stands for dynamic programming.
		lowerCAmelCase_   :							List[Any]									=			[[0 for i in range(__UpperCamelCase       )] for j in range(__UpperCamelCase       )]

		# since string of zero length match pattern of zero length
		lowerCAmelCase_   :							Optional[Any]									=			1

		# since pattern of zero length will never match with string of non-zero length
		for i in range(1      ,       __UpperCamelCase       ):
				lowerCAmelCase_   :							int									=			0

		# since string of zero length will match with pattern where there
		# is at least one * alternatively
		for j in range(1      ,       __UpperCamelCase       ):
				lowerCAmelCase_   :							Optional[int]									=			dp[0][j - 2] if pattern[j - 1] == "*" else 0

		# now using bottom-up approach to find for all remaining lengths
		for i in range(1      ,       __UpperCamelCase       ):
				for j in range(1      ,       __UpperCamelCase       ):
						if input_string[i - 1] == pattern[j - 1] or pattern[j - 1] == ".":
								lowerCAmelCase_   :							Optional[Any]									=			dp[i - 1][j - 1]

						elif pattern[j - 1] == "*":
								if dp[i][j - 2] == 1:
										lowerCAmelCase_   :							Optional[int]									=			1
								elif pattern[j - 2] in (input_string[i - 1], "."):
										lowerCAmelCase_   :							List[str]									=			dp[i - 1][j]
								else:
										lowerCAmelCase_   :							Tuple									=			0
						else:
								lowerCAmelCase_   :							int									=			0

		return bool(dp[-1][-1]       )


if __name__ == "__main__":
					import doctest

					doctest.testmod()
					# inputing the strings
					# input_string = input("input a string :")
					# pattern = input("input a pattern :")

					lowercase__          = """aab"""
					lowercase__          = """c*a*b"""

					# using function to check whether given string matches the given pattern
					if match_pattern(input_string, pattern):
										print(F"""{input_string} matches the given pattern {pattern}""")
					else:
										print(F"""{input_string} does not match with the given pattern {pattern}""")








"""simple docstring"""

import os

def 		__lowerCamelCase	(  )						->    Optional[Any]:

		"""simple docstring"""







		lowerCAmelCase_   :							Union[str, Any]									=			os.path.dirname(os.path.realpath(__UpperCamelCase       )       )
		lowerCAmelCase_   :							List[str]									=			os.path.join(__UpperCamelCase      ,       "triangle.txt"       )

		with open(__UpperCamelCase       ) as f:
				lowerCAmelCase_   :							Optional[int]									=			f.readlines()

		lowerCAmelCase_   :							Union[str, Any]									=			[]
		for line in triangle:
				lowerCAmelCase_   :							Any									=			[]
				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]       )       ):
						lowerCAmelCase_   :							Optional[Any]									=			a[i - 1][j] if j != len(a[i - 1]       ) else 0
						lowerCAmelCase_   :							int									=			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())
