Problem

A data processing pipeline consists of n services connected in series where the output of service i serves as input to service i+1. Each service has varying latency, and the throughput of the ith service is represented by throughput[i] in messages per minute.

Each service can be scaled up independently. Scaling up the ith service one unit of time costs scalingCost[i], and after scaling up x times, the service can process (throughput[i])^(1 + x) messages per minute.

Given throughput and scalingCost arrays of size n, and a budget value, determine the optimal scaling configuration to maximize the throughput of the final service. Return the maximum throughput possible.

Input

• int throughput[n]: the throughput generated by each of the n services
• int scalingCost[n]: the cost of scaling up a service one time
• int budget: the available money

Output

• long int: the maximum value of the throughput generated at the end of the composite service after scaling within the budget