Inspector Cat vs Monster Mouse Super Villain in the City of Superior Cheese === Fsshhhhh! Somewhere in a dark alley, in the City of Superior Cheese, a mysterious portal flashes into existence. WOOM! A man-sized mouse, draped in dark leather clothes, jumps out of the portal, running madly. Tingle-tingle! Fifteen blocks from there, Inspector Cat is enjoying a cup of milk when his wisker-senses kick in. Someone in the city must be trying to steal cheese from one of the few famous cheese shops of the city. Tingle-ti? Yes, his wiskers tell him exactly which shop it is, but it doesn't matter. Inspector Cat needs more information! Ting-tow tingloune tine-ti! So the fiend will try to escape through a portal at the intersection of Cheddar and Camembert? Then I shall wait for him there, challenge him, and bring him to justice! And Zoom!, Inspector Cat speeds through the streets towards the escape location. Of course, if Inspector Cat reaches the portal first (or if they arrive at the same time), then Monster Mouse has no chance to escape: Superheroes somehow always manage to win over Supervillains. But today, you're playing Monster Mouse. So you will need to plan routes which insure that the escape portal can be reached strictly before Inspector Cat. You will be given a map of the initial state of the city. Inspector Cat drinks milk at pixel 'C', 4 portals are represented by '*' pixels, while '.' pixels represent the ground. Monster Mouse, who begins in the alterworld, is not represented. The 4 cheese shops are represented by the numbers '1', '2', '4', and '8'. Those numbers are also the relative value of the cheese they contain. Monster Mouse wants to collect the maximum possible cheese value without ever getting caught by Inspector Cat. This maximum value is the integer your program should output. Monster Mouse first begins by picking a portal, and entering the City trough it. At this instant, both Monster Mouse and Inspector Cat already know which portal (not necessarily the same) will be used to exit to the alterworld. Naturally, Inspector Cat runs toward this exit portal immediately, but Monster Mouse must hold-up at least one cheese shop first. Otherwise, he won't have the strength to open the exit portal. Once Monster Mouse manages to reach the exit portal before Inspector Cat, he escapes, and recharges the super-powers which enable him to hold-up cheese shops in a blink of an eye, by merely touching them. Meanwhile, Inspector Cat finally reaches the exit portal, and awaits there with another cup of milk. Monster mouse may then pick another portal and collect more cheese, again and again until he decides it is no longer safe to do so. Portals can be used more than once, but not cheese shops. Since this takes place in a city, all distances are Manhattan distances. Inspector Cat and Monster Mouse move at the same pace.