





'''simple docstring'''




def 						__lowerCamelCase			(	UpperCAmelCase_							)   ->list[int]:
	snake_case__	       =   [0 for i in range(len(UpperCAmelCase_							)							)]

	# initialize interval's left pointer and right pointer
	snake_case__       ,  snake_case__	       =   0, 0

	for i in range(1					,				len(UpperCAmelCase_							)							):
		# case when current index is inside the interval
		if i <= right_pointer:
			snake_case__	       =   min(right_pointer - i + 1					,				z_result[i - left_pointer]							)
			snake_case__	       =   min_edge

		while go_next(UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_							):
			z_result[i] += 1

		# if new index's result gives us more right interval,
		# we've to update left_pointer and right_pointer
		if i + z_result[i] - 1 > right_pointer:
			snake_case__       ,  snake_case__	       =   i, i + z_result[i] - 1

	return z_result




def 						__lowerCamelCase			(	UpperCAmelCase_					,				UpperCAmelCase_					,				UpperCAmelCase_							)   ->bool:
	return i + z_result[i] < len(UpperCAmelCase_							) and s[z_result[i]] == s[i + z_result[i]]




def 						__lowerCamelCase			(	UpperCAmelCase_					,				UpperCAmelCase_							)   ->int:
	snake_case__	       =   0
	# concatenate 'pattern' and 'input_str' and call z_function
	# with concatenated string
	snake_case__	       =   z_function(pattern + input_str							)

	for val in z_result:
		# if value is greater then length of the pattern string
		# that means this index is starting position of substring
		# which is equal to pattern string
		if val >= len(UpperCAmelCase_							):
			answer += 1

	return answer


if __name__ == "__main__":
			import doctest

			doctest.testmod()










'''simple docstring'''




import os




def 						__lowerCamelCase			(	UpperCAmelCase_ = "input.txt"							)   ->int:

	with open(os.path.join(os.path.dirname(UpperCAmelCase_							)					,				UpperCAmelCase_							)							) as input_file:
		snake_case__	       =   [
		    [int(UpperCAmelCase_							) for element in line.split(','							)]
		    for line in input_file.readlines()
		]

	snake_case__	       =   len(UpperCAmelCase_							)
	snake_case__	       =   len(matrix[0]							)

	snake_case__	       =   [[-1 for _ in range(UpperCAmelCase_							)] for _ in range(UpperCAmelCase_							)]
	for i in range(UpperCAmelCase_							):
		snake_case__	       =   matrix[i][0]

	for j in range(1					,				UpperCAmelCase_							):
		for i in range(UpperCAmelCase_							):
			snake_case__	       =   minimal_path_sums[i][j - 1] + matrix[i][j]

		for i in range(1					,				UpperCAmelCase_							):
			snake_case__	       =   min(
			    minimal_path_sums[i][j]					,				minimal_path_sums[i - 1][j] + matrix[i][j]							)

		for i in range(rows - 2					,				-1					,				-1							):
			snake_case__	       =   min(
			    minimal_path_sums[i][j]					,				minimal_path_sums[i + 1][j] + matrix[i][j]							)

	return min(minimal_path_sums_row[-1] for minimal_path_sums_row in minimal_path_sums							)


if __name__ == "__main__":
			print(f"""{solution() = }""")



