A. AGM
time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ben found an old game box in his grandfather's basement and is looking forward to having $$$AGM$$$ (A Great Moment) playing it. In the box he found a game table with $$$12$$$ rows ($$$9-12$$$ are extra) and $$$6$$$ columns, $$$7$$$ types of pieces (which we will further call I, O, L, J, T, S, Z), and a description of the game:

  1. At he beginning of the game some cells become unavailable.
  2. In one move, Ben can ROTATE the current piece ONE step clockwise or counterclockwise or he can also MOVE the piece ONE column to the left, ONE column the the right or ONE row down.
  3. A move is considered VALID if, after performing the move, ALL elements of the piece are ON the table and NONE of the elements of the piece are placed on an unavailable spot.
  4. Ben can SET a piece ONLY if moving the piece down is not possible, all elements of the piece are on the table and NOT on the extra rows. After a piece is SET, all the spots corresponding to its elements become unavailable.
  5. As a result of setting a piece, some rows may have been filled with unavailable cells. We call this $$$AGM$$$ (A Great Moment). After an $$$AGM$$$, each of the filled rows on the table (regardless of the moment they were filled) is cleared and all the rows above it are shifted down 1 position. Let $$$R$$$ be the number of cleared rows after an $$$AGM$$$. Then, $$$\frac{R \times (R + 1) \times 100}{2}$$$ points will be added to Ben's score.
  6. At the very beginning, or when a piece is set, Ben takes the next piece and places it on the table with its origin on the $$$1$$$st column of the $$$12$$$th row. Note that Ben will always use the game pieces in the order that they are given to him by the All Mighty.
  7. After all the pieces are used, or the current piece cannot be set, the game ends.

Find below a description of each game piece. Notice how each of them fits into a $$$4 \times 4$$$ square matrix. Each black square represents an element of the piece. We'll consider the origin of each piece, the top left corner of this matrix. A rotation of ONE step corresponds to a transition between adjacent states of the same piece.

Ben wonders what is the maximum possible score that can be achieved by correctly using a given set of pieces. Can you help Ben out?

Input

The first line of the input contains the number of game pieces $$$N$$$ ($$$1 \leq N \leq 5$$$).

The second line contains a string of length $$$N$$$ containing the game pieces.

The following $$$8$$$ lines, each contain a string length $$$6$$$. The character '.' signifies an open position on the game table, while the character '#' signifies an unavailable position on the game table. No other characters are used.

Output

The output file should contain one integer representing the maximum possible score which can be obtained through strategic and well planned $$$AGM$$$s (A Great Moments).

Example
Input
4
ZLTI
###..#
###..#
###..#
###..#
###..#
......
......
#....#
Output
1100