Splitting a refund across payments

A guest paid for a trip in several pieces, possibly with different payment methods, and some of those pieces may already have been partly refunded. Now support wants to give back amount more. Decide how much of it goes back to each original payment.

def allocate_refund(
    payments: list[tuple[str, str, int, int]],
    past_refunds: list[tuple[str, str, int]],
    amount: int,
) -> list[tuple[str, int]]

payments[i] = (payment_id, method, timestamp, paid). Payment ids are unique. paid > 0, in cents.
past_refunds[j] = (refund_id, payment_id, refunded): an earlier refund of refunded cents against that payment. A payment may have several. Refunds that point to a payment id not in payments are ignored.

A payment's refundable balance is paid minus everything already refunded against it, never below 0.

Fill the new refund greedily, one payment at a time, in this priority order:

By method: "CREDIT" (platform credit) first, then "CARD", then "PAYPAL", then any other method, those in alphabetical order of the method name.
Within one method, the most recent payment first (larger timestamp); on equal timestamps, the smaller payment_id (string order) first.

Each payment takes min(its balance, what is still left to refund). Return the list of (payment_id, cents) in the order the refund was allocated, leaving out payments that receive 0.

amount >= 0. If the total refundable balance is less than amount, the refund is rejected: return []. amount == 0 also returns [].

payments = [
    ("p1", "CARD",   100, 5000),
    ("p2", "CREDIT", 50,  1000),
    ("p3", "CARD",   200, 3000),
    ("p4", "GIFT",   300, 2000),
]
past = [("r1", "p3", 2500), ("r2", "p2", 400)]
allocate_refund(payments, past, 4000)
# balances: p1 5000, p2 600, p3 500, p4 2000
# -> [("p2", 600), ("p3", 500), ("p1", 2900)]
allocate_refund(payments, past, 9000)   # [] : only 8100 is refundable

Constraints: up to 100,000 payments and 100,000 past refunds. Scanning all refunds for every payment is too slow; total them per payment first.