Let's get one thing straight: Halloween is all about the candy. And Little Billy is determined to get all of it. However, one of the neighbours seems to have had the same idea. They constructed a Haunted House to hide all of their candy so that only the truly worthy can get them. Little Billy managed to get his hands on the floor plan of house, and realized that this was no ordinary haunted house: it seems to be full of fake walls. Being his only imaginary friend who can program, help Little Billy get as much candy as possible as quickly as possible.
The input file DATA5.txt will contain 5 test cases. The first line of each test case is an integer 3 <= N <= 10, the number of rows and columns in the floor plan, followed by N lines (each N characters long), describing the floor plan.
- . - empty space
- # - unpassable wall
- B - Billy's start location
- * - piece of candy
- a-f (low case letters) fake walls
Fake walls are unlockable only if Billy has already collected at least as much pieces of candy as the order of the letter. That is, door "a" requires at least 1 pieces of candy. "b" = 2. "f" = 6.
The output file OUT5.txt will contain 5 lines of output, each a pair of non-negative integers C and S. C is the maximum number of candy pieces that Billy can collect. S is the minumum number of steps to do so.
3 B.* ##b ..* 5 B...* ####a .**.. #c#.. #*#..
1 2 4 11
Sample explanation: In in the first case, Billy collects the first piece on the second step, but that's not enough to make it through the wall "b". In the second case, Billy is able to collect all 4 pieces of candy.