고양이 배치 timer 1초 memory 1024MB

리처드는 대칭을 좋아하며, 현재 자신의 고양이들을 N \times M 크기의 격자로 나뉜 자신의 밭에 배치하려고 한다.

리처드는 대칭성을 유지하기 위해 다음과 같은 방식으로 고양이들을 배치한다:

• 밭의 가장 중앙 격자 칸에 고양이를 배치한다. 만약 그러한 중앙 격자 칸이 존재하지 않으면, 배치를 멈춘다.

• 배치를 했다면, 다음 밭을 네 개의 동일한 크기의 더 작은 밭으로 나누고(고양이가 있는 행과 열을 기준으로 나누어짐), 각 밭에서도 동일한 방식으로 고양이들을 배치한다.

• 밭을 더 작은 밭으로 계속 분할하는 과정을 중앙 격자 칸이 없거나 밭을 더 이상 나눌 수 없을 때까지 반복한다.

N = 7, M = 15인 경우, 리처드는 4행 8열에 고양이를 배치하고, 결과적으로 만들어진 3 \times 7 크기의 밭들 각각에 대해 동일한 작업을 수행한다. 3 \times 7 크기의 각 밭에서는 2행 4열에 고양이를 배치하고, 만들어진 1 \times 3 크기의 밭들 각각에 대해 동일한 작업을 수행한다. 아래는 그 과정의 시각적 예시이다(C는 고양이를 나타냄):

...............    ...............    .......|.......    .C.|.C.|.C.|.C.
...............    ...............    ...C...|...C...    ---C---|---C---
...............    ...............    .......|.......    .C.|.C.|.C.|.C.
............... -> .......C....... -> -------C------- -> -------C-------
...............    ...............    .......|.......    .C.|.C.|.C.|.C.
...............    ...............    ...C...|...C...    ---C---|---C---
...............    ...............    .......|.......    .C.|.C.|.C.|.C.

위 예시에서는 21마리의 고양이가 필요하다. 반면, N = M = 5인 경우에는 결과적으로 만들어진 2 \times 2 밭들에 중앙 격자 칸이 없으므로 고양이를 한 마리만 배치하면 된다. 리처드가 자신의 밭에 고양이를 배치하기 위해 몇 마리가 필요한지 구해보자.