Pick which tool servers to load for a task

Agent buildHard40 min

Your task

Every tool server an agent connects to puts its tool definitions in the context, and a big server costs thousands of tokens. A task needs a handful of capabilities, and the servers overlap in what they offer.

Write cheapest_servers(servers, needed) that returns the fewest tokens of tool definitions that cover every capability the task needs.

Input and output:

servers: up to 200 servers, each [tokens, capabilities]. tokens is a whole number from 0 to 1,000,000. capabilities is a list of up to 30 names.
needed: the names of the capabilities the task needs, at most 12 different ones. A name may be listed more than once.
Names are non-empty strings, compared exactly.
Return the smallest total of tokens over a set of servers that together offer every needed capability. Return 0 when nothing is needed, and -1 when no set of servers covers the task.

Rules:

Loading a server costs its tokens once, however many of its capabilities the task uses.
Capabilities the task does not need are worth nothing.

Examples

cheapest_servers(servers: list[list], needed: list[str]) -> int

Example 1

Input

cheapest_servers([[6000, ["read_file", "write_file", "run_tests"]], [4000, ["read_file", "write_file"]], [4000, ["run_tests", "open_pr"]], [5000, ["open_pr"]]], ["read_file", "write_file", "run_tests", "open_pr"])

Output8000

Example 2

Inputcheapest_servers([[1200, ["search_web"]], [900, ["read_file"]]], ["read_file", "send_email"])

Output-1

Example 3

Input

cheapest_servers([[300, ["calendar", "email"]], [700, ["email", "drive"]], [250, ["calendar"]]], ["email", "calendar", "email"])

Output300