Maximize Minimum Throughput

Problem Statement

Maximize Minimum Throughput A trading platform runs a pipeline of n independent services. Service i has a base throughput t[i] (requests per second) and a scaling price c[i] (the cost of adding one extra replica). If you add x[i] extra replicas to service i (with x[i] a non-negative integer), then the throughput of service i becomes (x[i] + 1) * t[i] , and the cost of scaling service i is x[i] * c[i] . The pipeline is only as fast as its slowest stage, so its overall throughput is min(throughput_1, throughput_2, ..., throughput_n) . You are given a total budget B . Choose the scaling amounts x[i] so that x[1]*c[1] + x[2]*c[2] + ... + x[n]*c[n] <= B and the pipeline throughput is as large as possible. Print that maximum pipeline throughput. Any leftover budget may simply go unspent. Input Format The first line contains a single integer n — the number of services. Each of the next n lines contains two space-separated integers t[i] and c[i] — the base throughput and the per-replica sca