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 sides on the grid lines) in the grid, and each small square in the grid has at least one of 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}
$$