A message pipeline is a chain of n services, and every message goes through all of them in order, so the pipeline moves only as many messages per second as its slowest service.
Service i handles rate[i] messages per second on one replica. You can add replicas: with r extra replicas it handles rate[i] * (1 + r). Each extra replica of service i costs cost[i], and you have budget to spend in total (you don't have to spend all of it).
Write max_throughput(rate: list[int], cost: list[int], budget: int) -> int that returns the largest pipeline throughput (the minimum over services of their scaled rate) you can reach.
max_throughput([4, 7, 5], [3, 10, 2], 9) # 7
max_throughput([4, 7, 5], [3, 10, 2], 25) # 14
max_throughput([3], [5], 12) # 9 two replicas, cost 10
max_throughput([6, 2], [1, 1], 0) # 2 no money, the slow service decides
In the first call, a replica of service 1 costs 10, more than the budget, so service 1 stays at 7 and the answer can't exceed 7. Reaching 7 costs 3 (one replica of service 0, giving 8) plus 2 (one of service 2, giving 10), which fits.
With budget 25, replicas (3, 1, 2) give rates (16, 14, 15) for 9 + 10 + 4 = 23. Reaching 15 would need two replicas of service 1 (cost 20) plus three of service 0 (cost 9), which is too much.
Constraints: 1 <= n <= 2 * 10**4, 1 <= rate[i], cost[i] <= 10**9, 0 <= budget <= 10**15. Buying replicas one at a time for the current bottleneck is correct but can take billions of steps; aim for about O(n log(answer)).
The inputs are such that the answer is below 4 * 10^18. In C++/Java, watch for 64-bit overflow anyway: a natural upper bound like rate[i] * (1 + budget / cost[i]) can reach 10^24, and so can a replica count times a cost, so clamp or compare before you multiply, and stop adding costs once they pass budget.
Show hint
if a throughput T is affordable, so is every smaller one, and checking one T takes a single pass: each service needs ceil(T / rate[i]) - 1 extra replicas.