A bakery has rolled out several rectangular sheets of shortbread. Sheet i is sheets[i] = (w, h) centimetres. Cookies are cut as squares of side s (a whole number of centimetres), aligned with the sheet edges, so one sheet yields (w // s) * (h // s) cookies. Leftover strips are thrown away; pieces from different sheets can't be joined.
Write biggest_side(sheets: list[tuple[int, int]], need: int) -> int that returns the largest side s >= 1 for which all the sheets together yield at least need cookies, or 0 if even s = 1 isn't enough.
Worked example with need = 5: with s = 3 the sheets give 3*2 + 1*1 = 7 cookies, and with s = 4 they give 2*1 + 1*1 = 3. So s = 3 is the answer:
biggest_side([(10, 7), (4, 4)], 5) # 3
biggest_side([(10, 7), (4, 4)], 3) # 4
biggest_side([(2, 3)], 7) # 0 (only 6 unit squares exist)
Constraints: up to 10^4 sheets, 1 <= w, h <= 10^9, 1 <= need <= 10^18. Trying every side from 1 upward can take up to 10^9 steps, so it's too slow. In C++/Java, stop adding once the running count reaches need: the full count can exceed 64 bits (one sheet alone gives up to 10^18 unit squares).
Show hint
the cookie count only goes down as s grows, so "count(s) >= need" is true, true, ..., true, false, false; binary search for the last s where it holds, with each check costing one pass over the sheets.