





from __future__ import annotations

from math import ceil, floor, sqrt

def       A__(		__lowerCAmelCase = 2_00_00_00 ):
				_snake_case :			list[int]  						=   [0]
				_snake_case :			int

				for idx in range(1	,			ceil(sqrt(target * 2 ) * 1.1 ) ):
								triangle_numbers.append(triangle_numbers[-1] + idx )

				# we want this to be as close as possible to target
				_snake_case :			int  						=   0
				# the area corresponding to the grid that gives the product closest to target
				_snake_case :			int  						=   0
				# an estimate of b, using the quadratic formula
				_snake_case :			float
				# the largest integer less than b_estimate
				_snake_case :			int
				# the largest integer less than b_estimate
				_snake_case :			int
				# the triangle number corresponding to b_floor
				_snake_case :			int
				# the triangle number corresponding to b_ceil
				_snake_case :			int

				for idx_a, triangle_a in enumerate(triangle_numbers[1:]	,			1 ):
								_snake_case :			Union[str, Any]  						=   (-1 + sqrt(1 + 8 * target / triangle_a )) / 2
								_snake_case :			List[str]  						=   floor(__lowerCAmelCase )
								_snake_case :			Tuple  						=   ceil(__lowerCAmelCase )
								_snake_case :			List[Any]  						=   triangle_numbers[b_floor]
								_snake_case :			List[Any]  						=   triangle_numbers[b_ceil]

								if abs(target - triangle_b_first_guess * triangle_a ) < abs(
								    target - best_product ):
												_snake_case :			Any  						=   triangle_b_first_guess * triangle_a
												_snake_case :			Optional[int]  						=   idx_a * b_floor

								if abs(target - triangle_b_second_guess * triangle_a ) < abs(
								    target - best_product ):
												_snake_case :			List[str]  						=   triangle_b_second_guess * triangle_a
												_snake_case :			Optional[Any]  						=   idx_a * b_ceil

				return area


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













from __future__ import annotations

def       A__(		__lowerCAmelCase	,			__lowerCAmelCase	,			__lowerCAmelCase ):
				_snake_case :			Dict  						=   list(range(len(__lowerCAmelCase ) ) )
				_snake_case :			Optional[int]  						=   [v / w for v, w in zip(__lowerCAmelCase	,			__lowerCAmelCase )]
				index.sort(key=lambda __lowerCAmelCase : ratio[i]	,			reverse=__lowerCAmelCase )

				_snake_case :			float  						=   0
				_snake_case :			list[float]  						=   [0] * len(__lowerCAmelCase )
				for i in index:
								if weight[i] <= capacity:
												_snake_case :			List[Any]  						=   1
												max_value += value[i]
												capacity -= weight[i]
								else:
												_snake_case :			Any  						=   capacity / weight[i]
												max_value += value[i] * capacity / weight[i]
												break

				return max_value, fractions


if __name__ == "__main__":
		import doctest

		doctest.testmod()






