Maximize Pipeline Throughput Under Budget

You are given a pipeline of n serial services. The base throughput of service i is t[i]. Since the services are in series, the overall pipeline throughput is defined as: throughput = min_i T_i You may scale each service. If you scale service i by x times (x is a non-negative integer), its throughput becomes: T_i = t[i] * (1 + x) The scaling cost is: cost = x * cost[i] Given a total budget, maximize the overall pipeline throughput without exceeding the budget. Output the maximum achievable overall throughput (as an integer). Input (stdin): n t[0..n-1] cost[0..n-1] budget Output (stdout): an integer: the maximum overall throughput Constraints: x is an integer, x >= 0 total scaling cost must be <= budget Example Input 3 3 5 2 5 1 3 0 Output 2