Program | KOCKE.C, KOCKE.CPP, KOCKE.PAS |
Little Matty liked playing with his blocks very much. He always constructed his "buildings" in the same way: he made stacks of one or more blocks, and he put those stacks on a square table that was exactly K blocks wide (K = 8 for his largest table, so it could contain up to 8×8 block stacks). He didn't put the stacks randomly on the table. No, he always made a nice "square" pattern. In most buildings, there was no pattern visible in the heights of the stacks. However, since Little Matty himself was only eight blocks tall, a single stack of blocks never consisted of more than eight blocks.
This is an example of one of his buildings. It was built on a table that could contain 4×4 block stacks.
He liked drawing too. To record his block buildings for future generations, he would draw them on paper. Since drawing a three-dimensional block building just was too hard for him, he made two drawings of a building: one straight from the front (you could only see the front of the blocks), and one from the right (you could only see the right side of the blocks). The drawings were in fact two-dimensional projections of the block building, showing only its outline on the front or on the right side.These are the drawings he made of the building shown above.
Front |
Right side |
Years later, looking again at the drawings, he realized that this was not the case: from most pairs of drawings, he was able to construct more than one building that had the same outlines (front and right side) as the original one. He found out that from every (front, side)-pair of drawings that he had made, he could construct a "minimal" building, one that has the same outlines as the original building and contains a minimal number of blocks N (so it was not possible to construct a building with the same outlines with less than N blocks). Furthermore, he could add more blocks to this minimal building, so that the outlines remained the same, up to the point that he had added M (M => 0) blocks and he had a "maximal" building, one that still had the same outlines as his minimal one, and adding one extra block would result in a building with a different outline (so there are no buildings with the same outlines that contain more than N + M blocks).
As an example, these are minimal and maximal buildings for the drawings shown above. In this case, N = 7 and M = 10.
Minimal Building |
Maximal Building |
Matty needs at least N blocks, and can add at most M extra blocks.
Sample Input
2
4
2 0 3 1
1 1 2 3
1
1
1
Sample Output
Matty needs at least 7 blocks, and can add at most 10 extra blocks.
Matty needs at least 1 blocks, and can add at most 0 extra blocks.