Как решить эту задачу с помощью жадного алгоритма (Python)

Рассмотрим шахматную доску с r строками и c столбцами. Найдите наибольшее количество королей, которых можно разместить на доске r×c, с выполнение следующих условий:

1. В любой клетке на доске может находиться не более одного короля.
2. У любого короля есть МИНИМУМ один возможный ход на свободную клетку на доске.

Формат ввода Единственная строка содержит два целых числа r и c.

Ограничения: 1≤r,c≤100.

Формат вывода Наибольшее количество королей.

Пример 1 Ввод: 5 1 Вывод: 3

Пример 2 Ввод: 3 3 Вывод: 8

Пример 3 Ввод: 4 4 Вывод: 12

Ограничение памяти 512.0 Мб Ограничение времени 2 с

Ввод стандартный ввод или input.txt

Вывод стандартный вывод или output.txt