Problem: brute1
After moving into their new house, Katie and Ben decide that their basement living area is too large and wish to add a wall in the middle. They cannot afford to pay a contractor, so they consider building a wall with the furniture already within the room. Katie has measured the minimum bounding boxes of each item and marked (with a one-foot accuracy) whether each portion of the bounding box is occupied or free of obstruction.
All furniture must remain upright and facing forward so that all of the drawers and cupboards remain usable from one of the sub-rooms. The furniture must span a 5'×5' area (yes, they're apparently midgets). To make a successful wall, there must be no holes remaining and all provided items must be used.
Input
The input contains several sets of furniture. Each set starts with a value 1 ≤ N ≤ 25, the number of pieces of furniture for this case. On the following line are two integers H and W with 1 ≤ H,W ≤ 5, representing the height and width of the bounding box of the first piece of furniture. There then follows H lines of length W containing 0s and 1s. '1' denotes that the piece of furniture occupies that space and '0' means that space is free. Every piece of furniture is assigned a letter (starting with 'A') by the order in which they are defined.
After the last piece of furniture may be a blank line, followed by the start of another test case, or EOF.
Output
For each test case, output should be a 5×5 grid showing the placements of each piece of furniture. Each position should have the letter of which piece of furniture occupies it. An extra blank line should be inserted between every test case. If multiple configurations exist, any one will do. If there is no solution, print "Frugality failure".
Sample Input
3 4 5 11111 11111 11111 11101 1 2 11 2 3 010 111 2 4 5 11111 11111 11111 10001 1 5 11111 5 1 3 111 2 3 011 110 3 5 00001 11111 10001 3 2 11 11 11 2 3 111 100
Sample Output
AAAAA AAAAA AAAAA AAACA BBCCC Frugality failure DDEEE DDEBB DDBBC CCCCC CAAAC