ACM 컴퓨터 공장

프로그래밍 대회에 쓰이는 컴퓨터는 모든 참가자가 동일한 조건에서 겨루도록 서로 완전히 같아야 하며, 그래서 하나의 공장에서 함께 생산된다.

컴퓨터 한 대는 $P$개의 부품으로 이루어진다. $P$개의 부품이 모두 갖추어지면 컴퓨터가 완성되어 출하할 수 있다.

조립은 $N$대의 기계로 완전히 자동화되어 있다. 각 기계는 조립이 진행 중인 컴퓨터를 받아 일부 부품을 떼어 내고 다른 부품을 붙인다(부품을 임의의 순서로 붙일 수 없어 때때로 부품을 먼저 떼어 내야 한다). 각 기계는 성능 $Q$(시간당 처리할 수 있는 컴퓨터 수), 입력 사양, 출력 사양으로 기술된다.

입력 사양은 $P$개의 값으로 이루어진 목록이며 각 값은 $0$, $1$, $2$ 중 하나이다. 부품 $j$에 대해 $0$은 그 부품이 없어야 함을, $1$은 있어야 함을, $2$는 있든 없든 상관없음을 뜻한다. 기계는 처리 중인 컴퓨터의 모든 부품 상태가 그 기계의 입력 사양과 맞을 때에만 작업할 수 있다.

출력 사양은 $P$개의 값으로 이루어진 목록이며 각 값은 $0$ 또는 $1$이다. 기계가 작업을 마치면 부품 $j$는 값이 $0$이면 없는 상태가, $1$이면 있는 상태가 되며, 이전 상태와는 무관하다.

기계들은 생산 라인으로 연결되며, 이동 시간은 처리 시간에 비해 무시할 수 있을 만큼 짧다. 아무 부품도 없는 빈 컴퓨터($P$개 부품이 모두 없음)가 투입되어 여러 기계를 차례로 거친 뒤 완성된 컴퓨터($P$개 부품이 모두 있음)로 나온다.

각 기계가 시간당 $Q$대를 넘겨 처리하지만 않는다면, 조립 중인 컴퓨터를 기계 사이에서 원하는 대로 흘려보낼 수 있다. 라인을 가장 잘 구성했을 때 이 공장이 시간당 만들어 낼 수 있는 완성된 컴퓨터는 최대 몇 대인가?

첫 줄에 두 정수 $P$와 $N$이 주어진다.

이어지는 $N$개의 줄에는 각각 기계 하나가 $2P + 1$개의 정수로 주어진다. 먼저 $Q_i$, 그다음 입력 사양 $S_{i,1}, S_{i,2}, \dots, S_{i,P}$, 마지막으로 출력 사양 $D_{i,1}, D_{i,2}, \dots, D_{i,P}$가 온다. 여기서 $Q_i$는 기계 $i$의 성능, $S_{i,j}$는 부품 $j$에 대한 입력 사양, $D_{i,j}$는 부품 $j$에 대한 출력 사양이다.

공장이 라인을 가장 잘 구성했을 때 시간당 생산할 수 있는 완성된 컴퓨터의 최대 개수를 정수 하나로 출력한다. 완성된 컴퓨터를 하나도 만들 수 없으면 $0$을 출력한다.

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