Maximize Pipeline Throughput Under Budget

Problem: Maximize Serial Pipeline Throughput Under Budget You have n services connected in series (service 1 -> service 2 -> ... -> service n). Service i has an initial throughput t[i]. The overall pipeline throughput is the minimum throughput among all services: [ throughput = \min_i {T_i} ] You may scale up each service: For service i, you can scale it x[i] times (x[i] is a non-negative integer). After scaling, its throughput becomes: [ T_i = t[i] \cdot (1 + x[i]) ] The scaling cost is: [ cost = x[i] \cdot cost[i] ] Given a total budget budget, choose x[i] values so that the total cost does not exceed budget and the overall pipeline throughput is maximized. Input format (stdin) Line 1: integer n Line 2: n integers t[1..n] Line 3: n integers cost[1..n] Line 4: integer budget Output format (stdout) Print one integer: the maximum achievable overall pipeline throughput. Constraints 1 <= n <= 2 * 10^5 1 <= t[i] <= 10^9 1 <= cost[i] <= 10^9 0 <= budget <= 10^18 x[i] must be a non-negative integer Example Example 1 Input: n = 3 t = [3, 5, 2] cost = [4, 2, 7] budget = 10 Output: 4 Explanation: To make overall throughput at least 4, scale service 3 from 2 to 4 (x=1, cost 7), others need no scaling. Total cost is 7 (<=10). Achieving 5 would exceed the budget, so the answer is 4. Example Input 3 3 5 2 4 2 7 10 Output 4