Задача . A. Освещение парка

В связи с эпидемией коронавируса власти города обязали жителей соблюдать социальную дистанцию. Мэр города Семён Сергеевич хочет осветить парк Глухарники, чтобы люди даже ночью могли видеть друг друга и соблюдали дистанцию.

Парк представляет из себя прямоугольную таблицу состоящую из \(n\) строк и \(m\) столбцов, где клетки таблицы — площади, а границы между клетками — улицы. Также улицами являются внешние границы. Каждая улица имеет длину \(1\). Например, у парка размера \(n=m=2\) всего \(12\) улиц.

Вам поручили разработать план освещения парка. Вы можете ставить фонари в серединах улиц. Фонарь освещает две площади, между которыми он стоит (или только одну площадь, если он стоит на границе парка).

Пример парка размеров: \(n=4\), \(m=5\). Освещенные площади отмечены жёлтым цветом. Обратите внимание, что все улицы имеют длины \(1\). Фонари ставятся в середины улиц. На картинке не все площади освещены.

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