XVIII математическая олимпиада «Шелковый путь», 2023 год

Дано натуральное $n$. В клетчатом квадрате $2n\times 2n$ каждая клетка покрашена в какой-то из $4n^2$ цветов (при этом некоторые цвета могли не использоваться). Доминошкой будем называть любой прямоугольник из двух клеток в нашем квадрате. Будем говорить, что доминошка разноцветная, если клетки в ней разных цветов. Пусть $k$ — количество разноцветных доминошек среди всех доминошек в нашем квадрате. Пусть $\ell$ — наибольшее целое число такое, что в любом разрезании квадрата на доминошки найдётся хотя бы $\ell$ разноцветных доминошек. Найдите наибольшее возможное значение выражения $4\ell - k$ по всем возможным раскраскам квадрата. ( И. Богданов )