Hide

Problem H
Hanjie

Hanjie, also known as Nonograms or Picross, are picture logic puzzles, where cells in a grid must be colored with black or white, according to numbers at the side of the grid:

\includegraphics[width=0.4\textwidth ]{h.png}

Formally, you are given a board with $r$ rows and $c$ columns. On each row and each column, you are also given a clue — a sequence $a_1, a_2, \ldots , a_ k$, meaning: If you iterate through the cells in this row (or column) from left to right (or from top to bottom), you will see:

  • zero or more consecutive white cells,

  • followed by exactly $a_1$ consecutive black cells,

  • followed by at least one consecutive white cells,

  • followed by exactly $a_2$ consecutive black cells,

  • followed by at least one consecutive white cells,

  • followed by exactly $a_ k$ consecutive black cells,

  • followed by zero or more consecutive white cells.

Note that it is possible for $a$ to be empty. In that case, all cells in that row (or column) should be white.

For example, consider the following row with $7$ columns and $a = 1, 2$:

The following row is valid:

\includegraphics[width=0.25\textwidth ]{h3.png}

The following two rows are not valid:

\includegraphics[width=0.25\textwidth ]{h2.png}
\includegraphics[width=0.25\textwidth ]{h4.png}

Given $r$, $c$ and the clues for each row and column, please count the number of different solutions satisfying all the clues. Two solutions are considered different, if there exists at least one cell with different colors.

Input

The first line of input contains $2$ integers $r$ and $c$ $(1 \le r, c \le 6)$.

The next $r$ lines, the $i$-th line contains the clue for the $i$-th row: a non-negative integer $k$ followed by $k$ positive integers $a_1, a_2, \ldots a_ k$, which satisfy $\sum _{i=1}^{k} a_ i + k - 1 \le c$.

The next $c$ lines, the $i$-th line contains the clue for the $i$-th column: a non-negative integer $k$ followed by $k$ positive integers $a_1, a_2, \ldots a_ k$, which satisfy $\sum _{i=1}^{k} a_ i + k - 1 \le r$.

Output

Output a single integer — the number of different solutions.

Sample Input 1 Sample Output 1
2 2
1 1
1 1
1 1
1 1
2

Please log in to submit a solution to this problem

Log in