<?xml version="1.0" encoding="Windows-1251"?>
<CATS version="1.0">
<Problem title="One is good, but two is better" lang="en" author="A. Klenin" tlimit="2" 
    inputFile="input.txt" outputFile="output.txt" stdChecker="nums">

<ProblemStatement>
 Given the <i>N</i> by <i>M</i> matrix with elements equal either 0, 1 or 2,
 There is at least one element equal to 2.
 Your program must find such two (perhaps overlapping or even identical) 
 rectangles, that they would contain all the 2s which are in matrix, but none of the 1s.
 If several solutions exist, the program must find a solution with minimal
 area of joined rectangles.
 For example, in the matrix
 <pre>
 1 2 1 0
 2 0 2 2
 1 2 1 0
 </pre>
 these rectangles are (2,1)-(2,3) and (1,2)-(4,2), with the combined area of 6.
</ProblemStatement>

<InputFormat>
  Input file contains integers <i>N</i> and <i>M</i> followed by <i>N</i> * <i>M</i> matrix elements. 
</InputFormat>

<OutputFormat>
  Output file must contain a single integer -- the minimal area, or -1 if no solution exists
</OutputFormat>

<ProblemConstraints>
 1 &amp;le; <i>N</i>, <i>M</i> &amp;le; 50
</ProblemConstraints>

<Sample rank="1">
  <SampleIn>3 4
1 2 1 0
2 0 2 2
1 2 1 0</SampleIn>
<SampleOut>6</SampleOut>
</Sample>

<!--Sloution name="sol" src="b.dpr" de_code="301"/-->
<!--Generator name="gen" src="gen.pas" de_code="201"/-->

<Generator name="g1" src="g1.pas" de_code="201"/>

<Test rank="1"><In src="d01.tst"/><Out src="d01.ans"/></Test>
<Test rank="2"><In src="d02.tst"/><Out src="d02.ans"/></Test>
<Test rank="3"><In src="d03.tst"/><Out src="d03.ans"/></Test>
<Test rank="4"><In src="d04.tst"/><Out src="d04.ans"/></Test>
<Test rank="5"><In src="d05.tst"/><Out src="d05.ans"/></Test>
<Test rank="6"><In src="d06.tst"/><Out src="d06.ans"/></Test>
<Test rank="7"><In src="d07.tst"/><Out src="d07.ans"/></Test>
<Test rank="8"><In src="d08.tst"/><Out src="d08.ans"/></Test>
<Test rank="9"><In src="d09.tst"/><Out src="d09.ans"/></Test>
<Test rank="10"><In src="d10.tst"/><Out src="d10.ans"/></Test>
<Test rank="11"><In src="d11.tst"/><Out src="d11.ans"/></Test>
<Test rank="12"><In src="d12.tst"/><Out src="d12.ans"/></Test>
<Test rank="13"><In src="d13.tst"/><Out src="d13.ans"/></Test>
<Test rank="14"><In src="d14.tst"/><Out src="d14.ans"/></Test>
<Test rank="15"><In src="d15.tst"/><Out src="d15.ans"/></Test>
<Test rank="16"><In use="g1"/><Out src="d16.ans"/></Test>

</Problem>
</CATS>
