Shipping rates

Price the parcels of a small online shop from its rate table, where one rule can be overridden by a more specific one.

Each rule is a string "region|category|flat|perkg". The region and the category are either an exact name or *, which matches anything. flat is the price in cents of the first kilogram, perkg is the price in cents of every further kilogram. A flat of X means the shop does not ship this combination (then perkg is ignored).

Each order is a string "region|category|grams". A rule applies to an order if its region matches the order's region and its category matches the order's category (names are case-sensitive). When several rules apply, the winner is chosen like this:

1. The rule with the most specific match wins, from most to least specific: exact region and exact category; exact region with * category; * region with exact category; * and *.
2. If two applicable rules are equally specific, the one that appears later in rules wins.

The weight is billed in whole kilograms, rounded up, and at least 1 kg: kg = max(1, ceil(grams / 1000)). The price of an order is flat + perkg * (kg - 1).

Input: rules, a list of rule strings, and orders, a list of order strings.

Output: a list of integers, one per order in the same order: the price in cents, or -1 if the winning rule is a X rule or no rule applies. If orders is empty, return [].