Фронтмен известной рок-группы Мэд построил в своем новом особняке оранжерею, которая представляет собой клеточное поле N × M. В оранжерее Мэд хочет посадить дронов двух моделей: «Бабочка» и «Ураган», при этом он хочет, чтобы дроны заняли все пространство оранжереи.

Каждый дрон имеет четыре ноги, которые при посадке занимают по одной клетке так, что эти клетки ограничивают квадрат со сторонами, параллельными границам оранжереи, а сам дрон занимает весь этот квадрат. При этом ноги дрона обязательно должны занимать разные клетки и могут быть расставлены как угодно широко.

Чтобы рассадка не выглядела слишком хаотично, Мэд хочет, чтобы дроны занимали квадраты одинаковых размеров, однако, чтобы внести разнообразие, никакие два дрона одной модели не должны касаться друг друга стороной, но могут касаться углами.

Необходимо помочь Мэду посадить как можно больше дронов.