Settle the Group Debts

Friends on a trip record each shared cost as (payer, amount, people): payer paid amount cents for the group people, a list of names that may include the payer. Everyone in people owes an equal share. When the amount does not divide evenly, the first amount % len(people) people in the list owe one cent more than the rest.

A person's balance is everything they paid minus everything they owe. To settle up, repeat these two steps until every balance is zero:

• Take the person with the largest positive balance (owed the most) and the person with the most negative balance (owing the most). Among equal balances, take the name that comes first in alphabetical order.
• The one who owes pays the other the smaller of the two amounts, what one is owed or what the other owes, which brings at least one of them to zero.

Write settle(expenses) that returns a list of the payments as (payer, receiver, amount) tuples, in the order they are made.

Examples

expenses = [
    ('Ana', 3000, ['Ana', 'Ben', 'Cy']),
    ('Ben', 1000, ['Ben', 'Cy']),
    ('Cy', 700, ['Ana', 'Ben', 'Cy', 'Dee']),
]
settle(expenses)
# returns [('Cy', 'Ana', 975), ('Ben', 'Ana', 675), ('Dee', 'Ana', 175)]

settle([('Kim', 100, ['Lee', 'Kim', 'Max'])])
# returns [('Lee', 'Kim', 34), ('Max', 'Kim', 33)]

In the first example the balances end up as Ana +1825, Ben -675, Cy -975 and Dee -175. In the second, 100 cents split three ways is 33 each with 1 cent left over, so Lee, first in the list, owes 34.

Constraints

• Up to 50,000 expenses and 20,000 people.
• Amounts from 1 to 1,000,000; each people list is non-empty with no repeated names.
• Names are compared with Python's normal string order.