Maximize pipeline throughput within a scaling budget

A message pipeline has n services in series, and every message passes through all of them. The pipeline's throughput is therefore the minimum throughput of any service.

You are given two integer arrays of length n:

• throughput[i]: the base throughput of service i.
• scaling_cost[i]: the cost of one upgrade of service i.

Upgrading service i a total of x times (x >= 0) raises its throughput to throughput[i] * (1 + x) and costs x * scaling_cost[i]. You may upgrade any service any number of times.

Implement max_throughput(throughput, scaling_cost, budget) -> int. It returns the largest pipeline throughput you can reach with total cost at most budget.

Constraints

• 1 <= n <= 10^5
• 1 <= throughput[i], scaling_cost[i] <= 10^9
• 0 <= budget <= 10^9

Example 1

throughput   = [3, 5]
scaling_cost = [2, 1]
budget       = 6
output       = 9

Two upgrades of service 0 (cost 4) bring it to 9, and one upgrade of service 1 (cost 1) brings it to 10. The total cost is 5, and the pipeline runs at min(9, 10) = 9. Reaching 10 would need three upgrades of service 0, for a total cost of 7, which is over budget.

Example 2

throughput   = [4, 6, 9]
scaling_cost = [5, 2, 3]
budget       = 0
output       = 4

With no budget, the slowest service sets the throughput.