Monthly AI token billing with plan switching

You are building the monthly invoice step for a chat-based AI product that charges by token usage. Each chat session produces one record, given as a comma-separated string with exactly four fields:

<user_id>,<input_tokens>,<output_tokens>,<plan>

plan is payg (pay as you go) or fixed. A user can have many sessions in the month.

Implement monthly_bills(sessions: list[str]) -> list[str] that returns one line per user, formatted "<user_id>: $<dollars>.<cents>" and sorted by user_id. List every user who appears, even if they owe $0.00.

Part 1: pricing

• Pay as you go: $0.02 per full 100 input tokens and $0.05 per full 100 output tokens. A partial block of fewer than 100 tokens is free. Blocks are counted on the user's monthly total, not per session.
• Fixed: a flat $20.00 per month that includes 50,000 input tokens and 25,000 output tokens. The two allowances are separate. Tokens above an allowance are billed at the pay-as-you-go rates, again in full 100-token blocks.
• Raise ValueError for a record that does not have 4 fields, has a negative token count, or names an unknown plan.

Part 2: plan switching

A user may have sessions on both plans in the same month. Prorate the fixed plan by sessions: if k of a user's n sessions are on fixed, the fee is $20.00 * k/n and each allowance is multiplied by k/n. Price the fixed sessions' tokens against the prorated allowances and the payg sessions' tokens at pay-as-you-go rates. Round the user's total to the nearest cent (half up) only once, at the end.

Constraints

• Up to 10^6 records; token counts are integers between 0 and 10^9.
• Money must be exact. Do not use floating point for amounts.

Examples

["ana,1250,480,payg", "ana,300,99,payg", "bo,60000,20000,fixed"]
-> ["ana: $0.55", "bo: $22.00"]

ana used 1,550 input tokens (15 blocks, $0.30) and 579 output tokens (5 blocks, $0.25). bo is 10,000 input tokens over the allowance (100 blocks, $2.00) on top of the $20.00 fee.

["cy,40000,30000,fixed", "cy,1000,1000,payg"]
-> ["cy: $22.45"]

Half of cy's sessions are fixed: fee $10.00, allowances 25,000 input and 12,500 output. Overage is 150 input blocks ($3.00) and 175 output blocks ($8.75). The payg session adds $0.20 + $0.50.