Начинающий огородник сделал грядку прямоугольной формы размером N на M клеток и в каждую клетку он может посадить одно растение. Он принял решение - вопрос №1862888

заняться выращиванием моркови, но у нее есть вредители, отпугивать которых огородник решил при помощи укропа. Одно растение укропа может защитить до 8 своих соседей (соседними растениями являются те, что растут в соседних клетках по вертикали, по горизонтали или по диагонали). У огородника есть K семян укропа. Помогите огороднику ответить на вопрос: сколько максимально можно вырастить моркови, затратив наименьшее количество семян укропа, при условии, что каждая морковь будет защищена укропом и как для этого нужно посадить на грядке морковь и укроп (огородника устроит любой допустимый вариант).