The Floor Bricks

Robert decorated the floor of his new room with a pattern made of oddly shaped, colourful bricks. When he was finished he noticed a problem: because the outline of the pattern is not a perfect rectangle, part of the floor is still bare. Because the bricks have such odd shapes, filling that bare strip completely is not easy. (A single unit-size brick does exist, but it is usually very expensive. Fig. 1 shows an example set of bricks.)

Robert is so proud of his arrangement that he refuses to move even one brick. Instead, he asks you to finish covering the bare floor with copies of the given bricks so that the total number of Gils spent is as small as possible. Bricks may not overlap, every bare cell must be covered, and no brick may stick out beyond the bare area. A brick may be rotated, but it may not be flipped over. You may assume that every brick fits inside a $3 \times 3$ box.

Fig. 1

Because the pattern already covers most of the floor, the bare region lies along the bottom edge of the rectangular floor. It can therefore be described by a series of integers that give, from left to right, how many unit cells are missing in each column. For example, the shape in Fig. 2 is described by the 11 integers 2 2 1 2 3 5 2 3 3 4 1. Each such integer is at most $5$. Fig. 3 shows a minimum-cost way to cover the floor with the brick set of Fig. 1.

Fig. 2

Fig. 3

The input contains at most $20$ test cases.

For each test case:

• The first line contains an integer $n$ ($1 \le n \le 1000$), the width of the floor.
• The second line contains $n$ integers separated by single spaces, describing the bare region as above: the number of missing unit cells in each column, from left to right. Each value is at most $5$.
• The third line contains an integer $m$ ($1 \le m \le 100$), the number of available brick types.
• The next lines describe the $m$ bricks. Each brick is given on four lines. The first line is a positive integer, the price of the brick in Gils. The following three lines each contain three characters describing the brick's shape: a dot (.) is empty space and a hash (#) is a unit block. The blocks of every brick are connected. Each brick type may be used any number of times.

A line containing a single 0 follows the last test case and must not be processed.

For each test case, print a single line Need at least g Gil(s)., where $g$ is the minimum number of Gils needed to cover the bare floor with the given bricks. If the floor cannot be covered, print Impossible. instead. Do not print blank lines between test cases.