<?xml version="1.0" encoding="Windows-1251"?>
<CATS version="1.2">
<Problem title="ACM Computer Factory" lang="en"
  author="T. Chistyakov" tlimit="1" mlimit="2"
  inputFile="input.txt" outputFile="output.txt">

<ProblemStatement>
 
 <p>As you know, all the computers used for ACM contests must be
 identical, so the participants compete on equal terms. That is why 
 all these computers are historically produced at the same factory. 
 </p><p>
 Every ACM computer consists of $P$ parts. When all these parts 
 are present, the computer is ready and can be shipped to one of 
 the numerous ACM contests.
 </p><p>
 Computer manufacturing is fully automated by using $N$ various 
 machines. Each machine removes some parts from a half-finished 
 computer and adds some new parts (removing of parts is 
 sometimes necessary as the parts cannot be added to a computer 
 in arbitrary order). Each machine is described by its 
 performance (measured in computers per hour), input and 
 output specification. 
 </p><p>
 Input specification describes which parts must be present 
 in a half-finished computer for the machine to be able to operate 
 on it. The specification is a set of $P$ numbers 
 0, 1 or 2 (one number for each part), where 0 means that 
 corresponding part must not be present, 1 -- the part is 
 required, 2 -- presence of the part doesn't matter. 
 </p><p>
 Output specification describes the result of the operation,
 and is a set of $P$ numbers 0 or 1, where 0 means that 
 the part is absent, 1 -- the part is present.
 </p><p>
 The machines are connected by very fast production lines 
 so that delivery time is negligibly small compared to
 production time.
 </p><p>
 After many years of operation the overall performance of the 
 ACM Computer Factory became insufficient for
 satisfying the growing contest needs. That is why ACM 
 directorate decided to upgrade the factory. 
 </p><p>
 As different machines were installed in different time periods, 
 they were often not optimally connected to the existing factory 
 machines. It was noted that the easiest way 
 to upgrade the factory is to rearrange production lines. 
 ACM directorate decided to entrust you with solving this problem. 
 </p>
</ProblemStatement>

<ProblemConstraints>
  $1 \le P \le 10, 1 \le N \le 50, 1 \le Q_i \le 10000$
</ProblemConstraints>

<InputFormat>
 Input file contains integers $P$ $N$, then 
 $N$ descriptions of the machines. The description of $i$th 
 machine is represented as by $2P + 1$ integers $Q_i S_{i,1}
 S_{i,2} \dots S_{i,P} D_{i,1} D_{i,2} \dots D_{i,P}$, 
 where $Q_i$ specifies performance, $S_{i, j}$ --
 input specification for part $j$, $D_{i, k}$ -- output 
 specification for part $k$.
</InputFormat>

<OutputFormat>
 <p>
 Output the maximum possible overall performance, then $M$ -- 
 number of connections that must be made, then $M$ descriptions 
 of the connections. Each connection between machines $A$ and $B$ 
 must be described by three positive numbers $A$ $B$ $W$, 
 where $W$ is the number of computers delivered from $A$ 
 to $B$ per hour. 
 </p><p>
 If several solutions exist, output any of them.
 </p>
</OutputFormat>

<Sample rank="1">
  <SampleIn>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</SampleIn>
  <SampleOut>25 2
1 3 15
2 3 10</SampleOut>
</Sample>

<Sample rank="2">
  <SampleIn>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</SampleIn>
  <SampleOut>4 5
1 3 3
3 5 3
1 2 1
2 4 1
4 5 1</SampleOut>
</Sample>

<Sample rank="3">
  <SampleIn>2 2
100  0 0  1 0
200  0 1  1 1</SampleIn>
  <SampleOut>0 0</SampleOut>
</Sample>

<Solution name="sol" src="factory.dpr"/>
<Checker src="fcheck.dpr" style="testlib"/>
<Module name="m1" src="gens.inc" type="generator" de_code="1"/>
<Generator name="g1" src="g1.dpr" outputFile="*STDOUT"/>
<Generator name="g2" src="g2.dpr" outputFile="*STDOUT"/>
<Generator name="g3" src="g3.dpr" outputFile="*STDOUT"/>
<Generator name="g4" src="g4.dpr" outputFile="*STDOUT"/>

<TestRange from="1" to="9"><In src="%0n.in"/><Out use="sol"/></TestRange>
<Test rank="10"><In src="10.in"/><Out use="sol"/></Test>

<Test rank="11"><In use="g1"/><Out use="sol"/></Test>

<Test rank="12"><In use="g2" param="1 2 2"/><Out use="sol"/></Test>
<Test rank="13"><In use="g2" param="1 5 5"/><Out use="sol"/></Test>
<Test rank="14"><In use="g2" param="2 5 5"/><Out use="sol"/></Test>
<Test rank="15"><In use="g2" param="3 10 7"/><Out use="sol"/></Test>

<Test rank="16"><In use="g3"/><Out use="sol"/></Test>

<Test rank="17"><In use="g4" param="5 5"/><Out use="sol"/></Test>
<Test rank="18"><In use="g4" param="5 10"/><Out use="sol"/></Test>
<Test rank="19"><In use="g4" param="7 7"/><Out use="sol"/></Test>
<Test rank="20"><In use="g4" param="10 5"/><Out use="sol"/></Test>

</Problem>
</CATS>
