Refund allocation across prioritized payment methods

A customer's order was paid with one or more payments, and some of them may already have been partly refunded. Implement a function that splits a new refund across those payments.

def allocate_refund(transactions: list[list[str]], refund: int) -> list[tuple[str, int]]: ...

Each transaction is a list of strings in one of two shapes:

• Payment: [payment_id, "PAYMENT", method, timestamp, amount], where method is CREDIT, CREDIT_CARD, or PAYPAL.
• Refund: [refund_id, "REFUND", payment_id, timestamp, amount], a refund already made against that payment.

All amounts are whole cents. Timestamps are integers.

Rules

1. A payment can give back only what is left on it: its amount minus all earlier refunds against it.
2. Refund by method first: all CREDIT payments, then CREDIT_CARD, then PAYPAL.
3. Within one method, refund the most recent payment first. Break exact ties by payment id.
4. Take as much as possible from each payment before moving to the next.
5. If the payments cannot cover the full refund, raise an error and allocate nothing.

Return a list of (payment_id, amount) pairs in the order the money is refunded. Skip payments that receive nothing.

Example

transactions = [
  ["a", "PAYMENT", "PAYPAL",      "10", "4000"],
  ["b", "PAYMENT", "CREDIT_CARD", "20", "2500"],
  ["c", "PAYMENT", "CREDIT",      "30",  "800"],
  ["d", "PAYMENT", "CREDIT_CARD", "40", "1500"],
  ["x", "REFUND",  "d",           "50",  "300"],
]
allocate_refund(transactions, 4000)
# -> [("c", 800), ("d", 1200), ("b", 2000)]

Credit c goes first. Card d is newer than b, but only 1200 is left on it after the earlier refund. The last 2000 comes from b, and PayPal is not touched. A request of 8501 or more raises an error, because only 8500 is refundable.

Constraints: up to 10^5 transactions; a refund always names a payment in the list, but it may appear before that payment.