II. (40 points) Given a $2016 \times 2016$ grid. Find the smallest positive integer $M$, such that it is possible to draw $M$ rectangles (with their sides on the grid lines) in the grid, and each small square in the grid has its sides included in the sides of one of the $M$ rectangles.
Second, $M=2017$.
First, we prove: All grid lines of a $2016 \times 2016$ square grid can be covered by the edges of 2017 rectangles.

In fact, all horizontal grid lines can be covered by the edges of 1008 $1 \times 2016$ rectangles and one $2016 \times 2016$ rectangle; all vertical grid lines can be covered by the edges of 1008 $2016 \times 1$ rectangles and the aforementioned $2016 \times 2016$ rectangle.
Thus, $M \leqslant 2017$.
Next, assume that the grid lines of a $2016 \times 2016$ square grid $A$ are covered by the edges of $M$ rectangles as required by the problem.
We will prove: $M \geqslant 2017$.
We call the top (bottom) edge of a rectangle the "head" ("foot").

For each rectangle in the grid $A$, we label it with a pair $(a, b)$: if the head of the rectangle is at the top of the grid $A$, we set $a=1$, otherwise $a=0$; if the foot of the rectangle is at the bottom of the grid $A$, we set $b=1$, otherwise $b=0$.

Among the $M$ rectangles, let the number of rectangles labeled $(1,1)$, $(1,0)$, $(0,1)$, and $(0,0)$ be $x$, $y$, $z$, and $w$, respectively.

There are 2015 horizontal grid lines inside the grid $A$, so $y+z+2w \geqslant 2015$;

There are 2017 vertical grid lines intersecting with the top of the grid $A$, so $2x+2y \geqslant 2017 \Rightarrow x+y \geqslant 1009$.
Similarly, $x+z \geqslant 1009$.
Thus, $2x+y+z \geqslant 2018$
$$
\begin{array}{l}
\Rightarrow 2(x+y+z+w) \geqslant 4033 \\
\Rightarrow M=x+y+z+w \geqslant 2017 .
\end{array}
$$