E. Light Up the Grid
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Little Q is testing a self-designed puzzle game involving a $$$2 \times 2$$$ grid where each cell can either be on or off. When a cell is toggled, its state changes from off to on or from on to off. The following four operations can be performed at a certain cost:

  • Toggle a single cell with cost $$$a_0$$$;
  • Toggle a row of cells with cost $$$a_1$$$;
  • Toggle a column of cells with cost $$$a_2$$$;
  • Toggle all cells with cost $$$a_3$$$.

Little Q has realized that the game has started, but the screen somehow malfunctions, blocking him from seeing the current state of any cell. The only feedback he can receive is a special prompt sound triggered if, after an operation, all cells are on.

Knowing all $$$m$$$ possible initial grids of the game in advance, Little Q wants to find a sequence of operations, ensuring that regardless of the initial grid when he starts playing, he will always hear the prompt sound after some operations in the order of the sequence.

Please calculate the minimum total cost of such sequence of operations.

Input

The first line of the input contains five integers $$$T$$$ ($$$1 \le T \le 10^4$$$), $$$a_0$$$, $$$a_1$$$, $$$a_2$$$, and $$$a_3$$$ ($$$1 \le a_0,a_1,a_2,a_3 \le 10^6$$$), indicating the number of games and the costs of each operation. For each game:

The first line contains an integer $$$m$$$ ($$$1 \le m \le 16$$$), indicating the number of possible initial grids of the game.

Then $$$m$$$ grids follow. For each grid:

  • There will first be an empty line if it is not the first grid in the game.
  • For the following two lines, the $$$i$$$-th line contains a string $$$s_{i,1}s_{i,2}$$$ of length $$$2$$$ consisting of characters 0 and 1, describing a $$$2 \times 2$$$ grid as a possible initial grid. Let $$$(i, j)$$$ be the cell on the $$$i$$$-th row and the $$$j$$$-th column. If $$$s_{i, j}$$$ is 0, then the cell $$$(i, j)$$$ is off, or otherwise the cell $$$(i, j)$$$ is on.

It is guaranteed that the given grids in a game are pairwise different.

Output

For each game, output a line containing an integer, indicating the minimum total cost.

Example
Input
2 1000 100 10 1
4
10
00

01
00

00
10

00
01
1
11
11
Output
1121
2