




'''simple docstring'''


def  _SCREAMING_SNAKE_CASE     (      UpperCamelCase__    :					str ,    UpperCamelCase__    :					str				):




     """simple docstring"""


     assert x is not None
     assert y is not None

     a_     :							Optional[int]     						=  len(UpperCamelCase__				)
     a_     :							int     						=  len(UpperCamelCase__				)

     # declaring the array for storing the dp values
     a_     :							List[Any]     						=  [[0] * (n + 1) for _ in range(m + 1				)]  # noqa: E741

     for i in range(1 ,    m + 1				):
          for j in range(1 ,    n + 1				):
               a_     :							Any     						=  1 if x[i - 1] == y[j - 1] else 0

               a_     :							Optional[int]     						=  max(l[i - 1][j] ,    l[i][j - 1] ,    l[i - 1][j - 1] + match				)

     a_     :							Dict     						=  """"""
     a_						,     a_     :							Union[str, Any]     						=  m, n
     while i > 0 and j > 0:
          a_     :							List[Any]     						=  1 if x[i - 1] == y[j - 1] else 0

          if l[i][j] == l[i - 1][j - 1] + match:
               if match == 1:
                    a_     :							Optional[int]     						=  x[i - 1] + seq
               i -= 1
               j -= 1
          elif l[i][j] == l[i - 1][j]:
               i -= 1
          else:
               j -= 1

     return l[m][n], seq


if __name__ == "__main__":
 lowerCAmelCase_      :  List[str]				     =  'AGGTAB'
 lowerCAmelCase_      :  Dict				     =  'GXTXAYB'
 lowerCAmelCase_      :  Optional[int]				     =  4
 lowerCAmelCase_      :  Any				     =  'GTAB'

 lowerCAmelCase_     ,   lowerCAmelCase_      :  List[Any]				     =  longest_common_subsequence(a, b)
 print('len =', ln, ', sub-sequence =', subseq)
 import doctest

 doctest.testmod()






'''simple docstring'''


def  _SCREAMING_SNAKE_CASE     (      UpperCamelCase__    :					list[int] ,    UpperCamelCase__    :					str				):




     """simple docstring"""


     a_     :							Tuple     						=  int(UpperCamelCase__				)

     # Initialize Result
     a_     :							Tuple     						=  []

     # Traverse through all denomination
     for denomination in reversed(UpperCamelCase__				):
          # Find denominations
          while int(UpperCamelCase__				) >= int(UpperCamelCase__				):
               total_value -= int(UpperCamelCase__				)
               answer.append(UpperCamelCase__				)  # Append the "answers" array

     return answer


# Driver Code
if __name__ == "__main__":
 lowerCAmelCase_      :  List[str]				     =  []
 lowerCAmelCase_      :  Union[str, Any]				     =  '0'

 if (
     input('Do you want to enter your denominations ? (yY/n): ').strip().lower()
     == "y"
 ):
  lowerCAmelCase_      :  str				     =  int(input('Enter the number of denominations you want to add: ').strip())

  for i in range(0, n):
   denominations.append(int(input(f"Denomination {i}: ").strip()))
  lowerCAmelCase_      :  Union[str, Any]				     =  input('Enter the change you want to make in Indian Currency: ').strip()
 else:
  # All denominations of Indian Currency if user does not enter
  lowerCAmelCase_      :  List[Any]				     =  [1, 2, 5, 10, 20, 50, 100, 500, 2000]
  lowerCAmelCase_      :  str				     =  input('Enter the change you want to make: ').strip()

 if int(value) == 0 or int(value) < 0:
  print('The total value cannot be zero or negative.')

 else:
  print(f"Following is minimal change for {value}: ")
  lowerCAmelCase_      :  Optional[int]				     =  find_minimum_change(denominations, value)
  # Print result
  for i in range(len(answer)):
   print(answer[i], end=' ')
