Implement an expiring GPU credits ledger

Implement an expiring GPU credits ledger for multiple users with three operations:

1. add_credit(user_id, amount, expiry_time): add a lot of credits that expires at expiry_time.
2. subtract(user_id, amount, timestamp): atomically deduct amount at timestamp by consuming unexpired lots in order of earliest expiry first; lots with expiry_time <= timestamp are expired and cannot be used; if total unexpired balance < amount, the operation must fail and make no changes.
3. get_balance(user_id, timestamp): return the total unexpired balance at timestamp and a breakdown by remaining lots (amount, expiry_time). Assumptions: time is integer seconds; amounts are non-negative integers; partial consumption of a lot is allowed; exact expiry boundary uses the rule "valid iff timestamp < expiry_time". Tasks: implement the three functions; include tests for (a) single lot add and spend, (b) spending across multiple lots with different expiries, (c) attempts to spend after a lot expires, (d) insufficient-balance failure leaving state unchanged, (e) edge case at expiry boundary. Follow up: analyze time/space complexity; discuss how to optimize for many operations (e.g., data structures to achieve O(log n) per update) and how to persist/restore state.