ACM Computer Factory

All computers used in a programming contest must be identical so that every participant competes on equal terms, so they are all built at a single factory.

Every computer consists of $P$ parts. A computer is complete once all $P$ parts are present, and only then can it be shipped.

Assembly is fully automated by $N$ machines. A machine takes a partially assembled computer, removes some parts, and adds others (removal is sometimes necessary because parts cannot always be added in an arbitrary order). Each machine has a performance $Q$ (how many computers it can process per hour), an input specification, and an output specification.

The input specification is a list of $P$ values, each $0$, $1$, or $2$: for part $j$, $0$ means the part must be absent, $1$ means it must be present, and $2$ means its presence does not matter. A machine can process a partially assembled computer only if every part matches the machine's input specification.

The output specification is a list of $P$ values, each $0$ or $1$: after the machine finishes, part $j$ is absent when the value is $0$ and present when it is $1$, regardless of its previous state.

Machines are linked by production lines whose transfer time is negligible compared with processing time. A blank computer (all $P$ parts absent) is fed in, is processed by a sequence of machines, and leaves complete (all $P$ parts present).

You may route the partially assembled computers between machines in any way, provided that no machine processes more than $Q$ computers per hour. Under the best possible routing, how many complete computers can the factory produce per hour?

The first line contains two integers $P$ and $N$.

Each of the next $N$ lines describes one machine using $2P + 1$ integers: $Q_i$, followed by the input specification $S_{i,1}, S_{i,2}, \dots, S_{i,P}$, followed by the output specification $D_{i,1}, D_{i,2}, \dots, D_{i,P}$. Here $Q_i$ is the performance of machine $i$, $S_{i,j}$ is its input specification for part $j$, and $D_{i,j}$ is its output specification for part $j$.

Print a single integer: the maximum number of complete computers the factory can produce per hour under the best routing of the production lines. If no complete computer can be produced, print $0$.

• $1 \le P \le 10$, $1 \le N \le 50$, $1 \le Q_i \le 10000$