Coin by Coin at the Market

The marginal utility of a good is the extra utility one more unit adds. For most goods it shrinks as you have more: the first loaf of bread matters a lot, the fourth hardly at all (diminishing marginal utility).

Pavel shops with budget coins and buys one unit at a time. goods is a dict name -> (price, mus): price is a whole number of coins and mus[k] is the marginal utility of the (k+1)-th unit, so mus[0] is what the first unit adds. The stall has only len(mus) units of that good. Before each purchase he looks at every good that still has a unit left and whose price he can still pay, and buys the next unit of the one with the highest marginal utility per coin, mus[k] / price (for the unit k he would buy next). Ties go to the cheaper good, then to the name that comes first alphabetically. He stops when no good qualifies.

Write coin_by_coin(budget, goods) that returns a tuple (units, left, total): a dict with the number of units bought of every good (0 if none), the coins left over, and the total utility (the sum of the marginal utilities of all units bought).

Examples

Input:  budget = 10, goods = {"apples": (2, [10, 8, 4, 2]), "bread": (3, [18, 9, 3])}
Output: ({'apples': 2, 'bread': 2}, 0, 45)
Explanation: bread first (18/3 = 6 per coin beats 10/2 = 5), then apples (5 beats 9/3 = 3),
apples again (8/2 = 4 beats 3), then bread (3 beats 4/2 = 2). 18 + 10 + 8 + 9 = 45.

Input:  budget = 6, goods = {"tea": (2, [6, 4]), "cake": (3, [9, 3])}
Output: ({'tea': 1, 'cake': 1}, 1, 15)
Explanation: tea and cake tie at 3 per coin, and tea is cheaper. Then cake (3 beats 4/2 = 2).
With 1 coin left nothing is affordable.

Constraints

• every price and marginal utility is a whole number, and each mus list never increases
• the tests contain exact ties between ratios, such as 9 / 3 and 6 / 2; compare ratios unrounded (fractions.Fraction or cross-multiplying makes the comparison exact)

Goals

• Compare goods by marginal utility per coin, $MU / p$, not by marginal utility alone
• Watch diminishing marginal utility spread spending across several goods
• Compare ratios exactly and apply a two-level tie rule