WhatWhat? Economy ----------------- Congratulations! You have been appointed the Economics Minister of the fabulous country What?What?. The economy of What?What? is doing well, but the Parliament and Prime Minister are demanding that you tell them how much better it can be if everyone just produces more and consumes more. Luckily for you, your predecessor compiled precise economic statistics before she left for the Asylum. Also lucky is the fact that What?What? has a one item economy. The good citizens, in their never ending quest for answers, decided some time ago that only Calories mattered, and "A Calorie is a Calorie is a Calorie, be it from carrots or spinach or steak!" So all the producers of What?What? produce Calories, the transporters transport Calories (all equal by law, regardless of weight or volume), and the consumers consume Calories, heedless of where they come from. Also the unit of money is the Calorie! What?What? has a bunch of towns connected by roads. Some towns have producers and some consumers and some both and some neither. Shipping is done by specifying a route that is a sequence of links. A link is a road between two towns plus the trucking company that transports Calories over the road. Each link has a capacity that depends mostly upon the number of What?What?iens who are willing to drive trucks over the road. There is a cost of transporting a Calorie over a link, expressed as a small positive number in units of Calories per Calorie. If there is a link from town X to town Y, there may or may not be a link from town Y back to town X, and if there is, the capacities and costs may differ. However, there is at most one link from any town X to any other town Y (the trucking companies are possessive). What you are to maximize is the sum of the Calories produced minus the Calories spent on transport. This is called the GCP: Gross Calorie Product. There is one more thing, however. Some links are run by Mafiosi who REQUIRE that a minimum number of Calories be transported over their links. Your predecessor found that to keep the Mafiosi happy, it was occasionally necessary to ship Calories in an aimless loop; though to keep costs down this had to be minimized. Input ----- Input consists of one or more test cases. Each test case begins with a test case name line. This is followed by a line with the format: N M where N is the number of towns and M the number of links. There follow N town description lines, each with the format: producer-capacity consumer-capacity which gives the maximum producer and consumer capacities for a town. The towns are indexed 1, 2, 3, ... N in the order of their town description lines. Then follow M link description lines, each with the format: s d capacity cost minimum which describes the link from town s to town d. The link has the given capacity in Calories, cost in Calories per Calorie, and minimum number of Calories that must be transported in order to satisfy the local Mafiosi. 2 <= N <= 20 1 <= M <= 100 0 <= producer-capacity <= 2,000 0 <= consumer-capacity <= 1,000 1 <= s,d <= N 1 <= capacity <= 1,000 0.01 <= cost <= 0.05 0 <= minimum <= capacity S <= 1,000.00 where S = sum over all links of: (capacity - minimum) * cost No two links have the same source and destination. All numbers are integers except cost which has 2 decimal places. Input ends with an end of file. No input line is longer than 80 characters. Output ------ For each case, output one line containing exactly the test case name, followed by one line containing either the maximum GCP with exactly 2 decimal places, or containing exactly the text: Mafiosi prevent solution! Sample Input ------ ----- -- SAMPLE 1 -- 4 4 100 0 0 0 0 100 0 0 1 2 1000 0.01 0 2 3 1000 0.05 0 2 4 1000 0.01 0 4 3 1000 0.01 0 -- SAMPLE 2 -- 4 3 100 0 0 100 0 0 0 0 1 2 1000 0.01 0 3 4 1000 0.01 200 4 3 1000 0.01 0 -- SAMPLE 3 -- 4 3 100 0 0 100 0 0 0 0 1 2 1000 0.01 0 3 4 1000 0.01 200 4 2 1000 0.01 0 -- SAMPLE 4 -- 4 4 100 0 0 100 100 0 0 100 1 2 1000 0.01 200 2 3 1000 0.01 0 3 4 1000 0.01 0 4 1 1000 0.01 0 Sample Output ------ ------ -- SAMPLE 1 -- 97.00 -- SAMPLE 2 -- 95.00 -- SAMPLE 3 -- Mafiosi prevent solution! -- SAMPLE 4 -- 194.00 File: economy.txt Author: Bob Walton Date: Mon Oct 10 12:04:32 EDT 2016 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file.