Welcome set budget

A conference buys a welcome set for every attendee, and each supplier covers one item in that set. Supplier i sells only in sealed packs holding pack_sizes[i] items at pack_cents[i] cents a pack, and a part used pack still costs a whole pack, so serving n attendees costs ceil(n / pack_sizes[i]) * pack_cents[i] at that supplier, added up over every supplier. Return the largest number of attendees the order can cover without the total passing budget_cents. The hall seats 100000 people, so never return more than 100000, and the answer never drops below 0, since serving nobody costs nothing. Pack sizes are at least 1, pack prices and the budget are never negative, and an order listing no suppliers at all costs nothing. Pricing one headcount touches every supplier, so halve the range rather than trying every headcount in turn.