



from __future__ import annotations






def 			lowerCAmelCase__	(					lowerCamelCase_	:	int):





				'''simple docstring'''

				lowerCAmelCase__  :       Optional[int]				=  str(lowerCamelCase_)
				return len(lowerCamelCase_) == 9 and set(lowerCamelCase_) == set('''123456789''')






def 			lowerCAmelCase__	(					):





				'''simple docstring'''

				for base_num in range(9999 ,4999 ,-1):
								lowerCAmelCase__  :       Union[str, Any]				=  100002 * base_num
								if is_9_pandigital(lowerCamelCase_):
												return candidate

				for base_num in range(333 ,99 ,-1):
								lowerCAmelCase__  :       Any				=  1002003 * base_num
								if is_9_pandigital(lowerCamelCase_):
												return candidate

				return None


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






from bisect import bisect
from itertools import accumulate






def 			lowerCAmelCase__	(					lowerCamelCase_	:	List[str] ,lowerCamelCase_	:	Optional[Any] ,lowerCamelCase_	:	List[str] ,lowerCamelCase_	:	Optional[int]):





				'''simple docstring'''

				lowerCAmelCase__  :       Any				=  sorted(zip(lowerCamelCase_ ,lowerCamelCase_) ,key=lambda lowerCamelCase_: x[0] / x[1] ,reverse=lowerCamelCase_)
				lowerCAmelCase__		,	lowerCAmelCase__  :       List[str]				=  [i[0] for i in r], [i[1] for i in r]
				lowerCAmelCase__  :       Tuple				=  list(accumulate(lowerCamelCase_))
				lowerCAmelCase__  :       str				=  bisect(lowerCamelCase_ ,lowerCamelCase_)
				return (
				    0
				    if k == 0
				    else sum(vl[:k]) + (w - acc[k - 1]) * (vl[k]) / (wt[k])
				    if k != n
				    else sum(vl[:k])
				)


if __name__ == "__main__":
							import doctest

							doctest.testmod()

