Европейская математическая олимпиада среди девочек (EGMO). 2026 год. Франция

Клетчатая доска $2026 \times 2026$ называется бордосской, если по крайней мере одна из её $2026^2$ клеток покрашена в красный цвет. Клетчатый прямоугольник назовём нечётным прямоугольником, если он содержит нечётное число красных клеток. Определите наибольшее натуральное число $M$ такое, что любая бордосская доска $2026 \times 2026$ содержит нечётный прямоугольник, в котором минимум $M$ клеток.
   Замечание: Клетчатый прямоугольник — это прямоугольник, состоящий из клеток доски. Эти прямоугольники содержат все свои внутренние клетки.