755. The Smallest Batch That Fits the Budget
A print shop has n job types. Job type i has a[i] pages and is charged w[i] rupees
per BATCH, where a batch is at most d pages and d is the same for every type. A job type of
a pages therefore uses ceil(a / d) batches and costs w * ceil(a / d).
You choose d. A smaller d means faster turnaround, so you want the smallest d whose total
cost stays within the budget B.
Print that smallest d, or -1 if no batch size is cheap enough.
pages 9 4 7, fees 2 1 3, B = 12 -> 5
pages 9 4 7, fees 2 1 3, B = 6 -> 9
pages 5 5 5 5, fees 1 1 1 1, B = 4 -> 5
pages 5 5 5 5, fees 1 1 1 1, B = 3 -> -1
At d = 5 the three types need 2, 1 and 2 batches, costing 2*2 + 1*1 + 3*2 = 11, inside 12.
At d = 4 they need 3, 1 and 2, costing 6 + 1 + 6 = 13.
## Why scanning d upward is too slow
d runs from 1 to 10^9 and each cost evaluation is O(n). That is 10^14 operations at the
limits, for a function that is trivially cheap to evaluate once.
## Why the predicate is monotone
The cost is
cost(d) = w[0] * ceil(a[0] / d) + ... + w[n-1] * ceil(a[n-1] / d)
Every weight is positive and every ceil(a / d) is non-increasing in d, so each term is
non-increasing and the sum is too. Raising d can only make the bill smaller or leave it alone,
never larger. So the batch sizes that fit the budget form a suffix and binary search applies.
The weights are what separates this from problem 751. There every job cost the same, so the
predicate was a plain count; here one expensive type can dominate the bill, and the cheapest way
to see that is to look at the tests where a single w is large.
## The bounds
lo = 1. hi = max(a), because at that batch size every type fits in one batch and the cost is
just sum(w), which is the cheapest the bill can ever be. Nothing larger than max(a) changes
anything, which is also why the answer can never exceed it.
## When the answer is -1
If sum(w) > B then even one batch per type is too expensive, and no d helps. Rather than
special-casing it, evaluate cost(hi) once before searching: if the cheapest possible bill is
already over budget, print -1.
## The boundary that breaks a careless implementation
The running total must stop as soon as it passes B. Without the early exit, d = 1 on the
largest input produces 10^5 terms of 1000 * 10^9, which is 10^17: still inside a signed
64-bit integer but well past the 2^53 where a JavaScript number stops being exact, and past a
32-bit integer by eight orders of magnitude. With the early exit the total never rises above
B + 1000 * 10^9, which every language handles exactly.
## Overflow
One term alone is up to 1000 * 10^9 = 10^12, so the accumulator is 64-bit everywhere and the
budget is read as a 64-bit value too.
## Related problems
Problem 751 is the unweighted version with a time limit instead of a budget, and it is worth solving first. Problem 763 keeps the weights out but gives every prefix its own deadline.
## Cost
Time O(n log(max a)). Space O(n).
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ B ≤ 10^12` - `1 ≤ a[i] ≤ 10^9` - `1 ≤ w[i] ≤ 1000`
Input
The first line contains two integers n and B, the number of job types and the budget.
The second line contains n integers a[0] ... a[n-1], the page counts.
The third line contains n integers w[0] ... w[n-1], the fee charged per batch of each type.
Output
Print one integer, the smallest batch size whose total cost is at most B, or -1 if no batch size is within budget. Print it alone on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.