SMO 2008 - Open - Vòng 2 Câu hỏi 5

Xét một bàn cờ $2008\times2008$. Gọi $M$ là số hình chữ nhật ít nhất có thể vẽ trên bàn cờ sao cho các cạnh của mọi ô đều được phủ bởi các cạnh của các hình chữ nhật đã vẽ. Tìm $M$. Ví dụ, với bàn cờ $2\times3$ thì $M=3$.