From Wheat Field to Bread Shelf

A loaf of bread sells for more than the wheat in it because each firm along the way adds something: the mill grinds, the bakery bakes. A firm's value added is

and GDP is the sum of every domestic firm's value added. (When nothing is imported, this equals the value of all final sales; it also gets the right answer when some inputs come from abroad.)

A regional statistician records every sale in a year as a triple (seller, buyer, amount), in thousands of crowns:

• seller is a firm's name or "abroad" (a foreign supplier: an import);
• buyer is a firm's name, "final" (households, the end of the chain) or "abroad" (a foreign customer: an export);
• seller != buyer. "final" and "abroad" are not firms.

Write value_added(sales) that returns a pair (by_firm, total): by_firm is a dict that maps every firm that appears in sales (as a seller or a buyer) to its value added, and total is the sum of those values. A firm that buys more than it sells has a negative value added; keep it.

Examples

Input:  sales = [("farm", "mill", 40), ("mill", "bakery", 90),
                 ("bakery", "final", 200), ("abroad", "bakery", 25)]
Output: ({"farm": 40, "mill": 50, "bakery": 85}, 175)
Explanation: the mill sells 90 and bought 40 of wheat: 50. The bakery sells 200
and bought 90 of flour and 25 of imported yeast: 85. Total 40 + 50 + 85 = 175,
which is less than the 200 of bread because 25 of it was made abroad.

Input:  sales = [("abroad", "final", 30)]
Output: ({}, 0)
Explanation: households buying imports directly involves no domestic firm.

Constraints

• numbers are compared with a tolerance of 1e-6

Goals

• Compute each firm's value added as its sales minus the inputs it bought
• Add up value added to get GDP without double counting
• Keep foreign suppliers and final buyers out of the firm list