HMMT 2002 U16

Divide an $m$-by- $n$ rectangle into $m n$ nonoverlapping 1-by-1 squares. A polyomino of this rectangle is a subset of these unit squares such that for any two unit squares $S, T$ in the polyomino, either (1) $S$ and $T$ share an edge or (2) there exists a positive integer $n$ such that the polyomino contains unit squares $S_{1}, S_{2}, S_{3}, \ldots, S_{n}$ such that $S$ and $S_{1}$ share an edge, $S_{n}$ and $T$ share an edge, and for all positive integers $k<n, S_{k}$ and $S_{k+1}$ share an edge.

We say a polyomino of a given rectangle spans the rectangle if for each of the four edges of the rectangle the polyomino contains a square whose edge lies on it.

What is the minimum number of unit squares a polyomino can have if it spans a 128 -by343 rectangle?