Price an agent run when prompt prefixes are cached

Your eval reports what each agent run cost. Every model call in a run sends a prompt made of blocks: the system prompt, the tool list, and one block per message. Your harness bills a block at a cheaper cached rate when the call's prompt opens with blocks that an earlier call in the same run also opened with.

Write run_cost(calls, tokens, full_rate, cached_rate) that returns the run's total cost.

Input and output:

• calls: the run's model calls in order, up to 10,000, each a list of block ids. There are up to 500,000 ids across all calls. A call may be empty, and it may hold the same id more than once.
• tokens: the size of each block in tokens, a whole number from 0 to 100,000, keyed by block id. Every id in calls is a key. Ids are non-empty strings, compared exactly, and one id always means the same content.
• full_rate, cached_rate: the price of one token, whole numbers from 0 to 1,000. cached_rate is at most full_rate.
• Return the total as a whole number.

Rules:

• A call's cached part is the longest run of blocks at its start that matches, block by block, the start of some earlier call in the same run.
• Each block in the cached part costs its tokens times cached_rate. Every other block costs its tokens times full_rate.
• The first call has no cached part.