The Tollkeeper's Rulebook

The tollkeeper of bitwick prices every crossing out of a single rulebook nailed inside her hut. A traveller is described by a handful of attributes, the whole book is consulted at once, and stronger rules override weaker ones.

Arguments

• rules — a list of strings: the rulebook, in order.
• traveller — a mapping from attribute name (string) to attribute value (string).

Rule format. Every rule is exactly "<conditions> => <action>". There is no whitespace beyond the single spaces shown.

The conditions are either the single character * (no conditions — the rule matches every traveller) or one or more terms key=value joined by &. A term matches when the traveller has that attribute and either value is * or the traveller's value for that attribute equals value. A rule matches when all of its terms match. No key appears twice within one rule.

The action is one of deny, allow, base N, add N, cap N, where N is an integer and may be negative.

Strength. Compare any two rules by, in this order: the number of terms (more wins), then the number of terms whose value is not * (more wins), then position in rules (later wins). This ranks every pair of rules.

Result. Considering only the rules that match the traveller:

1. Among the matching deny and allow rules, the strongest one wins. If it is a deny, return -1. If no deny or allow rule matches, the traveller passes. 2. The strongest matching base rule fixes the base fee. If no base rule matches, the base fee is 0. 3. Take the sum of the amounts of every matching add rule that is strictly stronger than the winning base rule — or, if no base rule matched, of every matching add rule. Add that sum to the base fee. 4. If any cap rule matches, the strongest one's N is an upper limit: the fee becomes the smaller of the fee and N. 5. Finally, a fee below 0 becomes 0.

Return the fee as an integer.