Маленький Петя любит заниматься дрессировкой пауков. У Пети есть доска размера n × m, в каждой клетке которой изначально сидит паук. Через одну секунду Петя быстро выбирает для каждого паука некоторое действие, и все они покорно выполняют свои команды. Всего есть 5 различных команд: остаться на месте или переползти из своей клетки в определенную из четырех соседних по стороне (то есть по одной команде на каждое из четырех возможных направлений). Петя дает команды таким образом, чтобы ни один паук не уполз за пределы доски. Допускается, что пауки могут ползти навстречу друг другу. Все пауки переползают одновременно, в одной клетке в итоге может оказаться более одного паука. Петя хочет знать, каким может быть максимальное возможное количество свободных от пауков клеток через одну секунду.