

def  UpperCAmelCase_   (_lowerCAmelCase :		Optional[Any]		):


			if not isinstance(SCREAMING_SNAKE_CASE__     ,			SCREAMING_SNAKE_CASE__		):
						raise TypeError("recursive_lucas_number accepts only integer arguments."		)
			if n_th_number == 0:
						return 2
			if n_th_number == 1:
						return 1

			return recursive_lucas_number(n_th_number - 1		) + recursive_lucas_number(
			    n_th_number - 2		)







def  UpperCAmelCase_   (_lowerCAmelCase :		Optional[int]		):


			if not isinstance(SCREAMING_SNAKE_CASE__     ,			SCREAMING_SNAKE_CASE__		):
						raise TypeError("dynamic_lucas_number accepts only integer arguments."		)
			__UpperCamelCase    :    List[str]								=      2, 1
			for _ in range(SCREAMING_SNAKE_CASE__		):
						__UpperCamelCase    :    str								=      b, a + b
			return a


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

					testmod()
					lowercase     :       Dict  	=       int(input("Enter the number of terms in lucas series:\n").strip())
					print("Using recursive function to calculate lucas series:")
					print(" ".join(str(recursive_lucas_number(i)) for i in range(n)))
					print("\nUsing dynamic function to calculate lucas series:")
					print(" ".join(str(dynamic_lucas_number(i)) for i in range(n)))


from __future__ import annotations







def  UpperCAmelCase_   (_lowerCAmelCase :		int     ,			_lowerCAmelCase :		list[int]     ,			_lowerCAmelCase :		list[int]     ,			_lowerCAmelCase :		int		):

			# Base Case
			if counter == 0 or capacity == 0:
						return 0

			# If weight of the nth item is more than Knapsack of capacity,
			#   then this item cannot be included in the optimal solution,
			# else return the maximum of two cases:
			#   (1) nth item included
			#   (2) not included
			if weights[counter - 1] > capacity:
						return knapsack(_lowerCAmelCase     ,			_lowerCAmelCase     ,			_lowerCAmelCase     ,			counter - 1		)
			else:
						__UpperCamelCase    :    Tuple								=      capacity - weights[counter - 1]
						__UpperCamelCase    :    List[str]								=      values[counter - 1] + knapsack(
						    _lowerCAmelCase     ,			_lowerCAmelCase     ,			_lowerCAmelCase     ,			counter - 1		)
						__UpperCamelCase    :    Dict								=      knapsack(_lowerCAmelCase     ,			_lowerCAmelCase     ,			_lowerCAmelCase     ,			counter - 1		)
						return max(_lowerCAmelCase     ,			_lowerCAmelCase		)


if __name__ == "__main__":
					import doctest

					doctest.testmod()