You hold n assets. Asset i is currently worth values[i], and you can upgrade it as many times as you like: each upgrade raises its worth by exactly 1 and costs costs[i]. You have a budget of total_cost to spend (you don't have to spend all of it).
The floor of the portfolio is the value of its least valuable asset. Return the largest floor you can reach.
def max_floor(values: list[int], costs: list[int], total_cost: int) -> int
max_floor([3, 5, 4], [2, 1, 3], 10)
# 5
# floor 5: raise asset 0 by 2 (cost 4) and asset 2 by 1 (cost 3): total 7 <= 10
# floor 6: needs 3*2 + 1*1 + 2*3 = 13 > 10
max_floor([7], [4], 9) # 9 (two upgrades cost 8; a third would cost 12)
max_floor([2, 9], [5, 1], 0) # 2 (no budget: the floor is the current minimum)
Constraints: 1 <= n <= 100,000, 0 <= values[i] <= 10^9, 1 <= costs[i] <= 10^4, 0 <= total_cost <= 10^15. With a budget this large, buying one upgrade at a time for the cheapest-to-lift asset is far too slow. Aim for about O(n log(total_cost)).
In C++/Java, one asset's cost (m - v) * c can exceed 64 bits when a candidate floor m is far above v (up to 10^15 * 10^4), so compare m - v with remaining_budget / c before multiplying.
Show hint
If a floor m is affordable, every smaller floor is too, so binary search on m. Reaching floor m costs sum((m - v) * c for v, c in zip(values, costs) if v < m); stop summing early once it exceeds the budget. The answer lies between min(values) and min(values) + total_cost // min(costs).