← 返回 uber 的题目列表Maximize Pipeline Throughput With Budgeted Scaling
类型：online_judge
You have a pipeline consisting of n serial stages. A request must pass stage 1 through stage n in order, so the overall throughput equals the minimum throughput among all stages (the bottleneck).
Each stage i starts with throughput cap[i]. You may scale up any stage using a limited budget: each scale operation on stage i increases its throughput by inc[i] and costs cost[i] budget; each stage can be scaled at most limit[i] times. Given total budget B, compute the maximum achievable overall pipeline throughput.
Input
Line 1: two integers n and B
Line 2: n integers cap[i]
Line 3: n integers inc[i]
Line 4: n integers cost[i]
Line 5: n integers limit[i]
Output
One integer: the maximum possible overall throughput.
Constraints
1 <= n <= 2e5
0 <= B <= 1e18
0 <= cap[i], inc[i], cost[i], limit[i] <= 1e9
Example
Input
3 10
3 2 5
2 3 1
2 4 3
3 2 10
Output
7
Example
Input
3 10
3 2 5
2 3 1
2 4 3
3 2 10
Output
7