



'''simple docstring'''




UpperCamelCase__       :	str    = range(2, 20 + 1)
UpperCamelCase__       :	List[Any]    = [10**k for k in range(ks[-1] + 1)]
UpperCamelCase__       :	dict[int, dict[int, list[list[int]]]]    = {}


def 				lowerCAmelCase_   (	_lowerCamelCase:   List[str]       ,      _lowerCamelCase:   str       ,      _lowerCamelCase:   Any       ,      _lowerCamelCase:   Optional[Any]					):
		__SCREAMING_SNAKE_CASE       :		str           =		sum(a_i[j] for j in range(_lowerCamelCase       ,      len(_lowerCamelCase					)					)					)
		__SCREAMING_SNAKE_CASE       :		List[Any]           =		sum(a_i[j] * base[j] for j in range(min(len(_lowerCamelCase					)       ,      _lowerCamelCase					)					)					)

		__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE       :		Any           =		0, 0
		__SCREAMING_SNAKE_CASE       :		Optional[Any]           =		n - i

		__SCREAMING_SNAKE_CASE       :		int           =		memo.get(_lowerCamelCase					)

		if sub_memo is not None:
				__SCREAMING_SNAKE_CASE       :		int           =		sub_memo.get(_lowerCamelCase					)

				if jumps is not None and len(_lowerCamelCase					) > 0:
						# find and make the largest jump without going over
						__SCREAMING_SNAKE_CASE       :		List[str]           =		-1
						for _k in range(len(_lowerCamelCase					) - 1       ,      -1       ,      -1					):
								if jumps[_k][2] <= k and jumps[_k][1] <= max_dn:
										__SCREAMING_SNAKE_CASE       :		Optional[Any]           =		_k
										break

						if max_jump >= 0:
								__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE       :		Optional[int]           =		jumps[max_jump]
								# since the difference between jumps is cached, add c
								__SCREAMING_SNAKE_CASE       :		Dict           =		diff + c
								for j in range(min(_lowerCamelCase       ,      len(_lowerCamelCase					)					)					):
										__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE       :		Union[str, Any]           =		divmod(_lowerCamelCase       ,      10					)
								if new_c > 0:
										add(_lowerCamelCase       ,      _lowerCamelCase       ,      _lowerCamelCase					)

				else:
						__SCREAMING_SNAKE_CASE       :		List[str]           =		[]
		else:
				__SCREAMING_SNAKE_CASE       :		str           =		{c: []}
				__SCREAMING_SNAKE_CASE       :		Tuple           =		sub_memo

		if dn >= max_dn or c + diff >= base[k]:
				return diff, dn

		if k > ks[0]:
				while True:
						# keep doing smaller jumps
						__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE       :		List[Any]           =		next_term(_lowerCamelCase       ,      k - 1       ,      i + dn       ,      _lowerCamelCase					)
						diff += _diff
						dn += terms_jumped

						if dn >= max_dn or c + diff >= base[k]:
								break
		else:
				# would be too small a jump, just compute sequential terms instead
				__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE       :		Any           =		compute(_lowerCamelCase       ,      _lowerCamelCase       ,      i + dn       ,      _lowerCamelCase					)
				diff += _diff
				dn += terms_jumped

		__SCREAMING_SNAKE_CASE       :		Any           =		sub_memo[c]

		# keep jumps sorted by # of terms skipped
		__SCREAMING_SNAKE_CASE       :		List[str]           =		0
		while j < len(_lowerCamelCase					):
				if jumps[j][1] > dn:
						break
				j += 1

		# cache the jump for this value digitsum(b) and c
		sub_memo[c].insert(_lowerCamelCase       ,      (diff, dn, k)					)
		return (diff, dn)


def 				lowerCAmelCase_   (	_lowerCamelCase:   Union[str, Any]       ,      _lowerCamelCase:   Tuple       ,      _lowerCamelCase:   str       ,      _lowerCamelCase:   str					):
		if i >= n:
				return 0, i
		if k > len(_lowerCamelCase					):
				a_i.extend([0 for _ in range(k - len(_lowerCamelCase					)					)]					)

		# note: a_i -> b * 10^k + c
		# ds_b -> digitsum(b)
		# ds_c -> digitsum(c)
		__SCREAMING_SNAKE_CASE       :		Optional[Any]           =		i
		__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE       :		Dict           =		0, 0, 0
		for j in range(len(_lowerCamelCase					)					):
				if j >= k:
						ds_b += a_i[j]
				else:
						ds_c += a_i[j]

		while i < n:
				i += 1
				__SCREAMING_SNAKE_CASE       :		int           =		ds_c + ds_b
				diff += addend
				__SCREAMING_SNAKE_CASE       :		Tuple           =		0
				for j in range(_lowerCamelCase					):
						__SCREAMING_SNAKE_CASE       :		str           =		a_i[j] + addend
						__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE       :		List[str]           =		divmod(_lowerCamelCase       ,      10					)

						ds_c += a_i[j]

				if addend > 0:
						break

		if addend > 0:
				add(_lowerCamelCase       ,      _lowerCamelCase       ,      _lowerCamelCase					)
		return diff, i - start_i


def 				lowerCAmelCase_   (	_lowerCamelCase:   Dict       ,      _lowerCamelCase:   int       ,      _lowerCamelCase:   Union[str, Any]					):
		for j in range(_lowerCamelCase       ,      len(_lowerCamelCase					)					):
				__SCREAMING_SNAKE_CASE       :		List[str]           =		digits[j] + addend
				if s >= 10:
						__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE       :		Union[str, Any]           =		divmod(_lowerCamelCase       ,      10					)
						__SCREAMING_SNAKE_CASE       :		Union[str, Any]           =		addend // 10 + quotient
				else:
						__SCREAMING_SNAKE_CASE       :		str           =		s
						__SCREAMING_SNAKE_CASE       :		List[str]           =		addend // 10

				if addend == 0:
						break

		while addend > 0:
				__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE       :		int           =		divmod(_lowerCamelCase       ,      10					)
				digits.append(_lowerCamelCase					)


def 				lowerCAmelCase_   (	_lowerCamelCase:   int = 10**15					):
		__SCREAMING_SNAKE_CASE       :		Union[str, Any]           =		[1]
		__SCREAMING_SNAKE_CASE       :		Tuple           =		1
		__SCREAMING_SNAKE_CASE       :		Optional[Any]           =		0
		while True:
				__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE       :		int           =		next_term(_lowerCamelCase       ,      20       ,      i + dn       ,      _lowerCamelCase					)
				dn += terms_jumped
				if dn == n - i:
						break

		__SCREAMING_SNAKE_CASE       :		int           =		0
		for j in range(len(_lowerCamelCase					)					):
				a_n += digits[j] * 10**j
		return a_n


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




'''simple docstring'''




def 				lowerCAmelCase_   (	_lowerCamelCase:   list[int]       ,      _lowerCamelCase:   str					):
		__SCREAMING_SNAKE_CASE       :		str           =		int(_lowerCamelCase					)

		# Initialize Result
		__SCREAMING_SNAKE_CASE       :		Tuple           =		[]

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

		return answer


# Driver Code
if __name__ == "__main__":
						UpperCamelCase__       :	int    = []
						UpperCamelCase__       :	List[Any]    = '''0'''

						if (
						    input('''Do you want to enter your denominations ? (yY/n): ''').strip().lower()
						    == "y"
						):
												UpperCamelCase__       :	Tuple    = 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()))
												UpperCamelCase__       :	str    = input('''Enter the change you want to make in Indian Currency: ''').strip()
						else:
												# All denominations of Indian Currency if user does not enter
												UpperCamelCase__       :	List[Any]    = [1, 2, 5, 10, 20, 50, 1_00, 5_00, 20_00]
												UpperCamelCase__       :	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}: ")
												UpperCamelCase__       :	int    = find_minimum_change(denominations, value)
												# Print result
												for i in range(len(answer)):
																		print(answer[i], end=''' ''')