Find the best accuracy a mix of agents buys

Your eval measured several agent setups on the same task suite, and each has an average cost per task and an accuracy. The product team can send each incoming task to a setup picked at random with fixed chances. For each budget the team asks about, they want the best accuracy such a mix can reach.

Write best_accuracy(agents, budgets) that returns the best accuracy for each budget.

Input and output:

• agents: up to 100,000 setups, each [cost, accuracy]. The cost per task is in hundredths of a cent, a whole number from 0 to 1,000,000. The accuracy is in hundredths of a percent, a whole number from 0 to 10,000. Setups may share a cost or an accuracy.
• budgets: up to 100,000 costs per task, in the same unit, each a whole number from 0 to 1,000,000.
• Return a list of floats, one per budget, in the same order. The tests accept any value within 0.000001 of the exact one.

Rules:

• A mix assigns each setup a chance of 0 or more, and the chances add up to 1. The mix's cost is the sum of each setup's cost times its chance, and its accuracy is the same sum over the accuracies.
• A single setup is a mix too, with a chance of 1.
• For each budget, return the largest accuracy of any mix whose cost is at most the budget. When every setup costs more than the budget, return -1. With no setups, return -1 for every budget.