ACM Computer Factory

Time limit1sMemory limit128 MB

Summary

Given machines with part-mask inputs, outputs, and hourly capacities, find the maximum factory throughput from the empty state to the full state.

Level: Medium7 of 10
Topics: Graph, BFS, Implementation
Solved: No attempts yet

Problem

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?

Input

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$ .

Output

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$ .

Constraints

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

Examples3

Example 1

Input

3 4
15  0 0 0  0 1 0
10  0 0 0  0 1 1
30  0 1 2  1 1 1
3   0 2 1  1 1 1

Expected output

Example 2

Input

3 5
5   0 0 0  0 1 0
100 0 1 0  1 0 1
3   0 1 0  1 1 0
1   1 0 1  1 1 0
300 1 1 2  1 1 1

Expected output

Example 3
Input
```
2 2
100  0 0  1 0
200  0 1  1 1
```
Expected output
```
0
```