ИДЗ по математической логике. Я в долгу не останусь!

[Lexa1208]

15. ПРЯМОУГОЛЬНОЕ СЖАТИЕ КАРТИНКИ
УСЛОВИЕ. Заданы (0 - 1) - матрица М порядка n x n и поло¬жительное целое число К-
ВОПРОС. Можно ли покрыть все единичные элементы мат¬рицы А не более, чем К прямоугольниками? Иначе говоря, су¬ществует ли такая последовательность четверок (ai, bi, сi, di), 1 ≤ i ≤ К, где аi ≤ bi, ci ≤ di, 1 ≤ i ≤ К, что для каждой пары индексов (i, j), 1 ≤ i ≤ K, Mij - равно 1 тогда и только тогда, когда существует такое k, 1 ≤ k ≤ К, что ak ≤ i ≤ bk и сk ≤ j ≤ dk?